【hiho】hiho第三十周·二分图染色判定

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#pragma warning(disable:4996)

#define Zero(a) memset(a, 0, sizeof(a))
#define Neg(a)  memset(a, -1, sizeof(a))
#define All(a) a.begin(), a.end()
#define PB push_back
#define repf(i,a,b) for(i = a;i <= b; i++)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,n,1
#define ld rt << 1
#define rd rt << 1 | 1
#define ll long long
#define MAXN 100005
#define mod 10007
using namespace std;

vector <int> mp[MAXN];
int col[MAXN];
int n, m;
void init(){
    scanf("%d %d", &n, &m);
    memset(col, 0, sizeof(col));
    for (int i = 1; i <= n; ++i) mp[i].clear();
    int u, v;
    for (int i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
}
bool dfs(int u, int color){
    col[u] = color;
    for (int i = 0; i < mp[u].size(); ++i){
        int v = mp[u][i];
        if (col[v]){
            if (col[v] != 3 - col[u]) return false;
        }
        else{
            if (!dfs(v, 3 - color))return false;
        }
    }
    return true;
}
bool solve(){
    for (int i = 1; i <= n; ++i){
            if (!col[i]){
                if (!dfs(i, 1))return false;
            }
        }
    return true;
}
int main(){
    int T;
    while (~scanf("%d", &T)){
        while (T--){
            init();
            if (solve())
                printf("Correct\n");
            else
                printf("Wrong\n");
        }
    }
    return 0;
}