posts - 225, comments - 62, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

1789

Posted on 2007-02-12 02:47 魔のkyo 阅读(182) 评论(0)  编辑 收藏 引用

 

// 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\n " ,accumulate(marked_person,marked_person + n, 0 ));
        delete [] vGroup;
        delete [] vPerson;
    }
}
只有注册用户登录后才能发表评论。