[Acwing] 860. 染色法判定二分图

前言

二分图有什么用呢,不知道,先学二分图的判定吧

思路

用st[]数组给每个点染上颜色 1和2 两种颜色

通过dfs遍历当前边的临边

(如果这个点已经被标记了 而且颜色相同 那么就不是二分图)

真简单吧,当初感觉难呢

CODE

#include 
using namespace std;
const int N = 1e5+10,M = 2e5+10;
int e[M],ne[M],h[N],idx;
int st[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] =idx++;
}

bool dfs(int u,int color)
{
    st[u] = color;
    for(int i=h[u];i; i=ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            if(!dfs(j,3-color)) return false;
        }
        else if(st[j]==color) return false;
    }
    return true;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    while(m -- )
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    bool flag = true;
    
    for(int i=1; i