TIOJ 1209 圖論 之 二分圖測試

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
bool ans = true;
struct node{
    int color;
    vector<int> edge;
};
node N[100005];

bool visit[100005];
void dfs(int x){
    if(!ans){ return; }
    if(visit[x]){ return; } 
    visit[x] = true;

    for (int i = 0; i < N[x].edge.size(); ++i){
        if(N[N[x].edge[i]].color == 0)
            N[N[x].edge[i]].color = N[x].color * -1;
        else if(N[N[x].edge[i]].color == N[x].color){
            ans = false;
            return;
        }

        if(!visit[N[x].edge[i]])
            dfs(N[x].edge[i]);
    }
}

int main(){
    int a, b;
    while(true){
        scanf("%d %d", &n, &m);
        if(n+m == 0){ break; }

        for (int i = 1; i <= n; ++i){
            N[i].color = 0;
            N[i].edge.clear();
            visit[i] = false;
        }

        for (int i = 0; i < m; ++i){
            scanf("%d %d", &a, &b);
            N[a].edge.push_back(b);
            N[b].edge.push_back(a);
        }
    
        ans = true;
        N[1].color = 1;
        dfs(1);

        printf("%s\n", ans? "Yes":"No");
    }
}