HDU 4751 Divide Groups 【判定二分图】

传送门
// 题意: 给定n个人之间的单方面认识关系, 要求把这n个人分到两个集合中, 要求同一集合中的人必须相互认识, 问是否可以做到.

// 思路: 很明显的, 这就是判定二分图, 先建图， 只要两个人之间相互认识, 他们之间就没有边, 否则就有边, 然后判定这个图是不是二分图就行啦.

判定二分图就是用染色法, 左边染1， 右边染2. 遇到要染的颜色和该点的颜色不同时就不是二分图了, 具体请看代码实现.

AC Code

const int maxn = 1e2+5;
int color[maxn];  // 左边染1， 右边染2
int g[maxn][maxn];
vector<int>G[maxn];
int flag;
void dfs(int u, int fa, int col) {
    if (!flag) return ;
    if (!color[u]) color[u] = col;
    else if (color[u] != col) {
        flag = 0;
        return ;
    }
    else return ;
    for (int i = 0 ; i < G[u].size() ; i ++) {
        int to = G[u][i];
        if (to == fa) continue;
        dfs(to, u, 3 - col);
    }
}
void solve()
{
    int n ;
    while(~scanf("%d", &n)) {
        Fill(color, 0); Fill(g, 0);
        flag = 1;
        for (int i = 1 ; i <= n ; i ++) {
            int u; G[i].clear();
            while(~scanf("%d", &u) && u) {
                g[i][u] = 1;
            }
        }
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = i + 1 ; j <= n ; j ++) {
                if (g[i][j] && g[j][i]) continue;
                G[i].pb(j);
                G[j].pb(i);
            }
        }
        for (int i = 1 ; i <= n ; i ++) {
            if (!color[i]) dfs(i, -1, 1);
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
}