Divide Groups(染色判断二分图） hdu 4751

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4751

题意：有n个人，其中列出每个人认识的人，问是否可以分成两组，使得每组中所有人都认识。

第一次判断二分图，一开始差点用强连通来做，但是发现要满足所有人都认识，就不行了，必须用染色法了。

每次DFS到下一个不属于同一阵营的人染上不同的颜色，同时判断是否不同阵营的人是否已经被染上同一种颜色，是的话就返回false。

#include<bits/stdc++.h>
#define maxn 200
#define in(a) scanf("%d",&a)
#define show(a) cout<<#a<<'='<<a<<endl
using namespace std;

struct side
{
    int next,v;
}edge[maxn*maxn];

vector<int> S[maxn];
int atlas[maxn][maxn],head[maxn],total,color[maxn];

bool dfs(int cur,int col)
{
    color[cur]=col;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(color[v]==-1&&!dfs(v,!col))
            return 0;
        if(color[v]==col)
            return 0;
    }
    return 1;
}

void add(int i,int j)
{
    edge[total].v=j;
    edge[total].next=head[i];
    head[i]=total++;
}

int main()
{
    int n,t;
    while(scanf("%d",&n)!=EOF)
    {
        total=0;
        memset(atlas,0,sizeof(atlas));
        memset(head,-1,sizeof(head));
        memset(color,-1,sizeof(color));
        for(int i=1;i<=n;i++)
            while(scanf("%d",&t)==1&&t)
            {
                atlas[i][t]=1;
            }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(!atlas[i][j]||!atlas[j][i])
                    {
                        add(i,j);add(j,i);
                    }
        int flag=1;
        for(int i=1;i<=n;i++)
            if(color[i]==-1&&!dfs(i,0))
            {
                flag=0;
                break;
            }
        if(flag)    printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}