poj 1611 The Suspects

    技术2025-10-25  7

    #include <iostream> using namespace std; int n,m,k,pre[30010],ran[30010]; void ini(int x) { pre[x]=x; ran[x]=0; } int findx(int x) { if(pre[x]==x) return x; pre[x]=findx(pre[x]); return pre[x]; } void unionset(int a,int b) { int t1=findx(a); int t2=findx(b); if(ran[t1]>ran[t2]) pre[t2]=t1; else pre[t1]=t2; if(ran[t1]==ran[t2]) ran[t2]++; } int main() { int i,j,b,c; while(scanf("%d%d",&n,&m)!=EOF) { if(m==0&&n==0) break; for(i=0;i<n;i++) ini(i); for(i=0;i<m;i++) { scanf("%d%d",&k,&b); for(j=1;j<k;j++) { scanf("%d",&c); if(findx(b)!=findx(c)) unionset(b,c); } } int t1=1; int t2=findx(0); for(i=1;i<n;i++) { if(findx(i)==t2) t1++; } printf("%d/n",t1); } return 0; }
    最新回复(0)