fork download
copy 
  1. <?php
  2. class DSU {
  3.     private $sz, $par;
  4.  
  5.     public function __construct($n) {
  6.         $this->sz = array_fill(0, $n, 1);
  7.         $this->par = range(0, $n - 1);
  8.     }
  9.  
  10.     public function getPar($u) {
  11.         if ($u == $this->par[$u]) {
  12.             return $u;
  13.         }
  14.         return $this->par[$u] = $this->getPar($this->par[$u]);
  15.     }
  16.  
  17.     public function connect($u, $v) {
  18.         $u = $this->getPar($u);
  19.         $v = $this->getPar($v);
  20.         if ($u != $v) {
  21.             if ($this->sz[$u] < $this->sz[$v]) {
  22.                 list($u, $v) = array($v, $u);
  23.             }
  24.             $this->sz[$u] += $this->sz[$v];
  25.             $this->par[$v] = $u;
  26.         }
  27.     }
  28. }
  29.  
  30. function unique(&$s) {
  31.     $s = array_values(array_unique($s));
  32. }
  33.  
  34. $dsu = new DSU(26);
  35.  
  36. fscanf(STDIN, "%d", $n);
  37. $used = array_fill(0, 26, false);
  38.  
  39. for ($i = 0; $i < $n; $i++) {
  40.     $s = str_split(trim(fgets(STDIN)));
  41.     sort($s);
  42.     unique($s);
  43.     foreach ($s as $ch) {
  44.         $used[ord($ch) - ord('a')] = true;
  45.     }
  46.     $k = count($s);
  47.     for ($j = 0; $j < $k - 1; $j++) {
  48.         $dsu->connect(ord($s[$j]) - ord('a'), ord($s[$j + 1]) - ord('a'));
  49.     }
  50. }
  51.  
  52. $parents = [];
  53. for ($i = 0; $i < 26; $i++) {
  54.     if ($used[$i]) {
  55.         $parents[] = $dsu->getPar($i);
  56.     }
  57. }
  58. sort($parents);
  59. unique($parents);
  60. echo count($parents) . "\n";
  61.  
Success #stdin #stdout 0.03s 26000KB
comments (?)
stdin
copy 
4
a
b
ab
d
stdout
copy 
2
https://ideone.com/zkXIFm
language:
PHP (php 7.3.5)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!