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 |
AC代码 500ms#include<cstdio> #include<iostream> using namespace std; const int maxn=31000; int pre[maxn],a[maxn],num[maxn]; int find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } void join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) { pre[fx]=fy; num[fy]+=num[fx]; num[fx]=0; } } int main() { int n,m,k; while(~scanf("%d%d",&n,&m),n+m) { for(int i=0; i<n; i++) pre[i]=i,num[i]=1;; while(m--) { scanf("%d",&k); for(int i=1; i<=k; i++) { scanf("%d",&a[i]); for(int j=1; j<i; j++) { join(a[i],a[j]); } } } printf("%d\n",num[find(0)]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator