POJ 4026 Eve

题目链接：http://livearchive.onlinejudge.org/external/59/5914.pdf

分析：并查集。相同祖先的放入同一个集合，每个集合可能有一个ID编号，也可能没有。

如果最后存在两个集合的ID为确定值且不相同，那么NO

如果最后所有集合都没有ID编号，或者只剩两个集合，一个有编号，一个没编号，那么POSSIBLY

如果最后所有的集合ID编号相同，或者只剩下一个集合，那么YES

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 
  5 const int MAXN = 200000 + 10;
  6 
  7 int p[MAXN];               //记录根节点编号
  8 bool isAlive[MAXN];        //判断是否存活
  9 bool isFemale[MAXN];       //记录是父亲还是母亲
 10 int temp[MAXN];            //记录ID
 11 int n, m, k;
 12 
 13 int find( int x )
 14 {
 15     return p[x] == x ? x : p[x] = find(p[x]);
 16 }
 17 
 18 int main()
 19 {
 20     int a, b;
 21     char ch;
 22     while ( scanf( "%d", &n ) != EOF )
 23     {
 24         for ( int i = 1; i <= n; i++ )
 25         {
 26             getchar();
 27             ch = getchar();
 28             if ( ch == 'F' ) isFemale[i] = true;
 29             else isFemale[i] = false;
 30             p[i] = i;
 31             isAlive[i] = true;
 32         }
 33 
 34         scanf( "%d", &m );
 35         int kk = n;
 36         for ( int i = 0; i < m; i++ )
 37         {
 38             scanf( "%d", &a );
 39             if ( a < 0 ) isAlive[ -a ] = false;
 40             else
 41             {
 42                 ++kk;
 43                 isAlive[kk] = true;
 44                 scanf( "%d %c", &b, &ch );
 45                 if ( ch == 'F' )
 46                     isFemale[kk] = true;
 47                 else isFemale[kk] = false;
 48 
 49                 if ( isFemale[a] ) p[kk] = find(a);
 50                 else               p[kk] = find(b);
 51             }
 52         }
 53 
 54         scanf( "%d", &k );
 55 
 56         for ( int i = 1; i <= m + n; i++ ) temp[i] = -1;   //每个节点的ID值初始化为-1，即标记为未知
 57 
 58         for ( int i = 0; i < k; i++ )
 59         {
 60             scanf( "%d%d", &a, &b );
 61             temp[ find(a) ] = b;
 62         }
 63 
 64         //   for ( int i = 1; i <= kk; i++ )
 65         //        printf( "fa[%d] = %d, temp[%d] = %d\n", i, p[i], i, temp[i] );
 66 
 67         int flag = 0;
 68         bool first = false;   //是否是第一次进入循环
 69         int x, y;
 70         for ( int i = 1; i <= kk; i++ )
 71             if ( isAlive[i] )
 72             {
 73                 x = find(i);
 74              //   printf( "temp[%d] = %d\n", x, temp[x] );
 75                 if ( first )
 76                 {
 77                     if ( x != y )         //若根节点不同
 78                     {
 79                         if ( temp[x] != temp[y] )     //若ID不同
 80                         {
 81                             if ( temp[x] != -1 && temp[y] != -1 )   //若存在一组，ID都是确定值
 82                             {
 83                                 flag = 1;    //那么存活下来的线粒体DNA肯定不同
 84                                 break;
 85                             }
 86                         }
 87                         if ( temp[x] == -1 || temp[y] == -1 )   //若存在一个不确定
 88                         {
 89                             flag = -1;
 90                         }
 91                     }
 92                 }
 93                 if ( temp[x] == -1 && first ) y = y;
 94                 else y = x;
 95                 first = true;
 96             }
 97 
 98         if ( flag == 1 ) puts("NO");
 99         else if ( flag == 0 ) puts("YES");
100         else puts("POSSIBLY");
101     }
102     return 0;
103 }