Divide Groups（分组）

题目大意是说输入数字n

然后告诉你第i个人都认识谁？

让你把这些人分成两堆，使这每个堆里的人都互相认识。

做法：把不是互相认识的人建立一条边，则构建二分图，两堆的人肯定都互相认识，也就是说，互相认识的两个人肯定不相连。

——代码

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int n, cnt;

 int head[], to[], next[], color[];

 bool know[][];

 void add(int x, int y)

 {

     to[cnt] = y;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 //把点染成1或-1

 bool dfs(int u, int c)

 {

     int i, v;

     color[u] = c;

     for(i = head[u]; i != - ; i = next[i])

     {

         v = to[i];

         if(color[v] == c) return ;

         if(color[v] ==  && !dfs(v, -c)) return ;

     }

     return ;

 }

 bool solve()

 {

     int i;

     for(i = ; i <= n; i++)

      if(color[i] ==  && !dfs(i, ))

       return ;

     return ;

 }

 int main()

 {

     int i, j, x;

     while(~scanf("%d", &n))

     {

         memset(know, , sizeof(know));

         memset(color, , sizeof(color));

         for(i = ; i <= n; i++)

           while(scanf("%d", &x) && x)

           know[i][x] = ;

         memset(head, -, sizeof(head));

         for(i = ; i <= n; i++)

          for(j = i + ; j <= n; j++)

           if(!know[i][j] || !know[j][i])

           {

               add(i, j);

               add(j, i);

           }

         if(solve()) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

巴特西

Divide Groups（分组）

最新文章

热门文章