二分圖判定：染色法

二分圖判定方法：染色法

∙ \bullet ∙對于一個二分圖的兩個集合，假設給同一個集合裡的點都染上一樣的顔色，那麼為了區分這兩個集合，就把另一個集合的點染成另外一種顔色。很明顯：一條比對邊的兩個頂點顔色肯定不一樣。

∙ \bullet ∙對于一個圖，判斷是不是二分圖，就可以用染色法來判定。任意從一個頂點A出發，将它染上色，再找與它相連的頂點B，假設A與B之間的邊是比對邊，那麼就有兩種情況：

1.如果B與A的顔色相同，就代表這個圖不是二分圖。

2.B還沒有染色，就将B染成與A不同的顔色，再找與B相連的頂點，如果遇到1的情況，不是二分圖。

1、2這個過程可以用dfs來完成。

∙ \bullet ∙例題： http://acm.hdu.edu.cn/showproblem.php?pid=4751

∙ \bullet ∙思路：将單向認識或者互相不認識的兩個人之間建雙向邊，再判定是不是二分圖。反證法證明思路的正确性：如果最終确定是一個二分圖，那麼假設在一個集合中有兩個頂點它們不是互相都認識，那麼它們就不可能在同一個集合，這個圖也不是二分圖，證畢。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn = 1e3+10;
const int inf = 999999999;
int k,m,n;
int co[maxn],mp[maxn][maxn];

struct node{int to,next;}e[maxn*10];
int head[maxn],cnt = 0;
void add(int s,int E){
    e[ ++ cnt] = {E,head[s]};
    head[s] = cnt;
}
int flag = 0;
bool dfs(int x,int c)
{
    co[x] = c;
    for(int i = head[x];i != -1;i = e[i].next){
        int to = e[i].to;
        if(co[to] == co[x])
            return false;
        if(co[to] == 0 && dfs(to,-c) == false)///如果與x相連的to結點沒有染色，并且dfs與to相連的結點遇到了相同的顔色
            return false;
    }
    return true;///兩種情況都沒有發生傳回真
}

void init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(e,0,sizeof(e));
    memset(co,0,sizeof(co));
    memset(mp,0,sizeof(mp));
}

void input()
{
    for(int i = 1;i <= n;i++){
        int x;
        while(scanf("%d",&x) && x){
            mp[i][x] = 1;
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = i + 1;j <= n;j++){
            if(!(mp[i][j] == 1 && mp[j][i] == 1)){
                add(i,j);
                add(j,i);
            }
        }
    }
}
int main()
{
    while(scanf("%d",&n) != EOF){
        init();
        input();
        int flag = 0;
        for(int i = 1 ; i <= n ; i ++ ){
            if(co[i] == 0)
                if(dfs(i,1) == false){
                    flag = 1;
                    break;
                }
        }
        if(flag == 0)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}