Disjoint Set Union
PHP
Hard
6 views
Problem Description
Commands: UNION a b, FIND a b. FIND prints YES if connected else NO.
Input Format
First line q. Next q lines.
Output Format
Outputs for FIND.
Sample Test Case
Input:
5
UNION 1 2
FIND 1 3
UNION 2 3
FIND 1 3
FIND 2 2
Constraints
Values are 1..200000.
Official Solution
<?php
class DSU{
private $p=[]; private $r=[];
function make($x){ if(!isset($this->p[$x])){ $this->p[$x]=$x; $this->r[$x]=0; } }
function find($x){
$this->make($x);
if($this->p[$x]!==$x) $this->p[$x]=$this->find($this->p[$x]);
return $this->p[$x];
}
function union($a,$b){
$ra=$this->find($a); $rb=$this->find($b);
if($ra===$rb) return;
if($this->r[$ra]<$this->r[$rb]){ $t=$ra; $ra=$rb; $rb=$t; }
$this->p[$rb]=$ra;
if($this->r[$ra]===$this->r[$rb]) $this->r[$ra]++;
}
function connected($a,$b){ return $this->find($a)===$this->find($b); }
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$q=intval($inputLines[0]);
$dsu=new DSU(); $output=[];
for($i=1;$i<=$q;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''));
$cmd=$tokens[0] ?? '';
$a=intval($tokens[1] ?? 0);
$b=intval($tokens[2] ?? 0);
if($cmd==='UNION') $dsu->union($a,$b);
else $output[] = $dsu->connected($a,$b) ? 'YES' : 'NO';
}
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!