【數據結構】量子危機

問題

宇宙時間公元 5.55 億年，由于某種原因兩大聯盟展開了激戰（maxingc 聯盟采用了微子技術）：
邪惡的 maxingc 聯盟采集好了微子能，就要運輸。Maxingc 聯盟的領袖 xc 此時才發現，自己的軍事基地中
由微子發射器組成的微子能量網存在很大的問題，于是他決定修改。
之前，TT 為了整齊，把軍事基地建成了矩形，而且如果兩個微子發射器的連線平行于軍事基地的一邊，這
兩個微子發射器之間就一定有微子能量傳輸線相連。
(*注：比如有 3 個微子發射器A（1，1）、B（1，3）、C（2，2），那么 A 和 B 之間有微子能量傳輸線相連，
A 和 B 不能傳輸到 C。*)
但是在微子能運輸過程中發現，常常不能從一個微子發射器運抵另一個微子發射器。
為了可以從任何一個微子傳輸器能運抵其它任意一個微子傳輸器，而且能和原來的微子能量網同樣整齊，
TT 決定遵循原來的規則，調動他的百萬農奴新修建一些微子能量傳輸線和微子發射器。由于微子發射器的
造價比微子傳輸線高得多，所以 TT 決定忽略微子能量傳輸線的成本。
但是 TT 又不想花費不必要的錢，所以找到你為他計算最少需要建多少個微子發射器。
輸入格式? Input Format
第一行三個正整數 n、m、p。(2<=n,m<=100000，表示軍事基地的兩邊長；2<=p<=200000，表示微子

發射器的個數。)
接下來 p行，每行兩個正整數數 Xi、 Yi(1<=Xi<=n?? 1<=Yi<=m)，代表每個微子發射器在軍事基地的位置。
（可能會由于疏漏，有些微子發射器重復）
輸出格式? Output Format
樣例:
?輸入：5 6 6
1 1
2 2
2 4
3 3
5 1
5 5
輸出：
2
只有一行，為最少修建微子發射器的數量。
樣例的一種方案：
#.....
|#-#..
|.#+..
|.|...
#-+-#.
#表示原有微子發射器，-、|表示微子能量傳輸線，+表示興建的微子發射器。所以至少興建 2 個微子發射
器。

分析

我們先這樣考慮，如果對所有已知的節點進行染色的話，能染成同一種顏色的節點一定在同一個強連通分量中(內部連同)，那么需要興建的節點數就等于強連通分量數減一

我們來證明這個結論：對于任意一個節點它可以照顧到一行一列上的所有節點。也就是說，一個節點最多可以連接到4個強連通分量。如果一個興建的節點只連接一個強連通分量，那么這個節點是毫無用處的。如果一個節點連接3個強連同分量，那么這3個強連通分量必有兩個已經在一個強連通分量中。連接4個同理。只有當一個節點連接兩個強連通分量時，才能讓這兩個原先不連通的分量相互連同。

這就類似于最小生成樹，將興建的節點看成邊，原有的強連通分量看做節點，那么n個節點連成一顆生成樹必然需要n-1個節點。

下面的問題就是如何染色。

如果用floodfill會很復雜，而且顯然會超時。我們要考慮更加優秀的的算法。我們現在需要將在一個強連通分量中的原節點賦予同一個標識，并查集！

再加一個標記數組（n+m 表示某行或某列上是否有節點）。每讀入一個節點我們就將其所在的行和列和并在一個集合中。這樣就將一個強連同分量中的所有行和列合并在了同一個集合中。

最后，只需要枚舉每行（列），如果該行（列）被標記過（在某個強連通分量中），那么找到它的根節點，累計總數并且標記當前強連通分量被訪問過（應用并查集壓縮路徑后在同一個集合中的元素的祖先相同），只需標記其祖先即可。

program liukeke;
var
f:array[1..400000] of longint;
v:array[1..400000] of boolean;
i,n,m,p,x,y,temp1,temp2,ans:longint;

function find(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;

begin
assign(input,'wei.in');reset(input);
assign(output,'wei.out');rewrite(output);
readln(n,m,p);
for i:=1 to n+m do f[i]:=i;
for i:=1 to p do
begin
readln(x,y);
temp1:=find(x);
temp2:=find(y+n);
if temp1<>temp2 then
f[temp1]:=temp2;
v[x]:=true;
v[y+n]:=true;
end;
for i:=1 to n+m do
if v[i] then
begin
temp1:=find(i);
if v[temp1] then
begin
inc(ans);
v[temp1]:=false;
end;
end;
writeln(ans-1);
close(input);
close(output);
end.

反思

要先對題目分析，抽象其模型，再選取合適的數據結構解決問題，并查集應用不多但都很巧妙，可用來判斷邏輯關系和集合關系