1789

// 2007-02-12 02:13:52    Accepted    1789    C++    00:00.04    2988K // 一次AC // 算法：分支限界法（用队列搜） #include  < iostream > #include  < vector > #include  < queue > #include  < numeric > using   namespace  std;typedef vector < int >  vector_int; int  main () ... {    int n,m;    while(scanf("%d %d",&n,&m)!=EOF && (n||m))...{        int marked_person[30000]=...{1},marked_group[500]=...{0};//标记有嫌疑的人，和有嫌疑的组        queue<int> Q;//用来BFS有嫌疑的组        vector_int* vGroup=new vector_int [m];        vector_int* vPerson=new vector_int [n];        for(int i=0;i<m;i++)...{            int k,t;            scanf("%d",&k);            for(int j=0;j<k;j++)...{                scanf("%d",&t);                vGroup[i].push_back(t);//Group i中有t这个成员                vPerson[t].push_back(i);//Person t参加了i这个组                if(!t)...{                    marked_group[i];//标记所有包含0这个成员的Group                    Q.push(i);//有嫌疑的组入队                }            }        }        while(!Q.empty())...{            int tempQNode=Q.front();//取出一个嫌疑组            Q.pop();            for(int i=0;i<vGroup[tempQNode].size();i++)...{//遍历嫌疑组中的所有人                int tempPerson=vGroup[tempQNode][i];                if(!marked_person[tempPerson])...{//如果这个人没有被标记过                    marked_person[tempPerson]=1;//标记嫌疑人                    for(int j=0;j<vPerson[tempPerson].size();j++)...{//遍历这个人所加入的所有组                        int tempGroup=vPerson[tempPerson][j];                        if(!marked_group[tempGroup])...{//如果嫌疑人加入的组没有被标记过                            marked_group[tempGroup]=1;//标记嫌疑组                            Q.push(tempGroup);//嫌疑组入队                        }                    }                }            }        }        printf("%d ",accumulate(marked_person,marked_person+n,0));        delete [] vGroup;        delete [] vPerson;    }}