用并查集合并不同的集合
Sample Input
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
Sample Output
Yes
Yes
No
View Code
#include<iostream> using namespace std; #define size 5001 int father[size]; int find(int k) { return father[k]==k?k:father[k]=find(father[k]); } int main() { int n, m, p, former, later; cin>>n>>m>>p; for(int i=1; i<=n; i++) father[i]=i; for(int i=0; i<m; i++) { cin>>former>>later; father[find(former)]= find(later); //將其中一個集合的根結點全部賦值到另一個集合的根結點,這樣就能將兩個不同的集合合并了 } //上面的合并并不是真正意義上的合并,因為只用根結點進行了合并,并沒有將所有點進行合并 //真正的合并的做法是,從頭到尾再合并一次就可以了 //for(int i=1; i<=n; i++){ // father[i] = find(i); //} //這個很重要啊~~~~~~~~~~~~~~~~ //只要加上了這句話,下面就可以直接用f[]=?f[]了。 for(int i=0; i<p; i++) { cin>>former>>later; if(find(former)==find(later)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
posted on 2011-10-29 20:49 More study needed. 閱讀(470) 評論(0) 收藏 舉報

浙公網安備 33010602011771號