793-Network Connections

<br /> /* <br /> "Network Connections"<br /> Level:4.0<br /> Date:2007/3/2<br /> 技巧: <br /> 利用Union-Find Algorithm & path compresssion<br /> 'c': union(node1,node2)<br /> 'q': Find_Set(node1) == Find_Set(node2) <br /> */<br /> <br /> #include <iostream><br /> #include <stdio.h><br /> <br /> using namespace std;<br /> <br /> int Find_Set(int); //回傳該node所屬的集合的代表node. <br /> void Link(int,int); //相連兩個集合樹. <br /> void Union(int,int); //聯集(呼叫前兩個function). <br /> <br /> const int MAX_N = 30001;<br /> <br /> int p[MAX_N], //儲存每個node的parent. <br /> rank[MAX_N]; //儲存每個node的高度.<br /> <br /> int main()<br /> {<br /> int num,n,node1,node2,yes,no;<br /> char op;<br /> char input[6]; <br /> <br /> cin >> num;<br /> <br /> while(num--)<br /> { <br /> yes = no = 0; <br /> cin >> n;<br /> for(int i=1; i <= n; i++){ p[i]=i; rank[i]=0; } cin.ignore(); while(gets(input) != NULL && sscanf(input,"%c %d %d",&op,&node1,&node2)==3) { if(op == 'c') Union(node1,node2); else if(op == 'q'){ if(Find_Set(node1) == Find_Set(node2)) yes++; else no++; } } cout << yes << "," << no << endl; if(num) cout << endl; } // while(1); } int Find_Set(int x) { //若x不是root, 便將parent指向root, 並回傳root node. if(x != p[x]) p[x] = Find_Set(p[x]); //recursive find root. return p[x]; } void Link(int x, int y) { if( x == y) //x,y屬同一個Set, 不需相連. return; //小樹串到大樹下. if(rank[x] > rank[y]){<br /> p[y] = x;<br /> } <br /> else{<br /> p[x] = y;<br /> if(rank[x] == rank[y]) //兩棵樹一樣高時, 合成樹的高度會長高一個單位. <br /> rank[y]++; <br /> } <br /> }<br /> <br /> void Union(int x, int y)<br /> { <br /> Link(Find_Set(x),Find_Set(y)); //找到兩個node分屬的Set, 並將兩個set相連. <br /> }<br />