Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
为何总是WA呢?--------郁闷,第一次写并查集#include<iostream> using namespace std; int rank[30001]; int cluster[30001]; int findCluster(int pos) { if(cluster[pos]==pos) { return pos; } return cluster[pos]=findCluster(cluster[pos]); } void Merge(int i1,int i2) { int j1=findCluster(i1); int j2=findCluster(i2); if(j1==j2) return; if(rank[j1]>rank[j2]) { cluster[i2]=j1; } else { cluster[i1]=j2; if(rank[j1]==rank[j2]) { rank[j2]++; } } } //利用并查集来解POJ1611问题 void func(int N,int K) { //看了蜗居,人生真是艰难 //初始化 for(int i=0;i<30001;i++) cluster[i]=i; for(int i=0;i<30001;i++) rank[i]=0; for(int k=0;k<K;k++) { int temp; cin>>temp; int temp1; cin>>temp1; for(int i=1;i<temp;i++) { int temp2; cin>>temp2; Merge(temp1,temp2); } } int sum=0; for(int i=0;i<N;i++) { if(findCluster(i)==findCluster(0)) { sum++; } } cout<<sum<<endl; } int main() { int N,K; cin>>N; cin>>K; while(true) { if(N==0&&K==0) { break; } if(K==0) { cout<<"1"<<endl; } else { func(N,K); } cin>>N>>K; } system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator