Hiho一下 二分图1 Week33

HiHo

描述

简单的讲是这样，有个人开了个婚介所，然后呢，有n个人报名，他就点鸳鸯谱嘛（把两个编号的人安排相亲），结果点的太多他怕有疏漏然后把同性给安排了。所以现在给你n个人(不知道男女)，和m对相亲关系，判断他的安排对不对，对的话就输出Correct否则就输出Wrong。

输入

第1行：1个正整数T(1≤T≤10)
接下来T组数据，每组数据按照以下格式给出：
第1行：2个正整数N,M(1≤N≤10,000，1≤M≤40,000)
第2..M+1行：每行两个整数u,v表示u和v之间有一条边

输出

第1..T行：第i行表示第i组数据是否有误。如果是正确的数据输出”Correct”，否则输出”Wrong”

样例输入

2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5

样例输出

Wrong
Correct

思路

直接DFS就好了，选定一个点作为初始点，将其染色，入队列。每次从队列中取出点，遍历其相连的点，如未染色，则染上与该点不同的颜色，并如队列；若已经染色且二者同色，就说明两个人是gay嘛，那就报错。如果队列空了，那看看有没有还没有染色的点，有的话就入列重复以上操作（防止图不联通），没有的话就输出'Correct'。

代码

#include<iostream>
#include<cstdio>
#include<vector>  
#include<queue> 
using namespace std;
typedef vector<int> vint;
int n,m;
void solve(){
    cin >> n >> m;
    vector <vint> G(n+1);
    short color[10001];
    for(int i=0;i<=n+1;i++) color[i] = 2;
    queue <int> q;
    int a,b;
    while(m--){
        scanf("%d%d",&a,&b); 
        G[a].push_back(b);
        G[b].push_back(a);
    }
    color[1]=0;
    q.push(1);
    bool flag = true;  
    while(flag){
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for (int i=0;i<G[t].size();i++){
            if(color[G[t][i]]==2){
                q.push(G[t][i]);
                color[G[t][i]] = !color[t];
            }else {
                if(color[G[t][i]]==color[t]){
                    cout << "Wrong"<<endl;
                    return;
                }
            }
        }
    }
    flag = false;
    for(int i=1;i<=n;i++)
        if(color[i]==2){
            color[i] = 0;
            q.push(i);
            flag = true;
            break;
        }
    }
    cout<< "Correct"<<endl;
    return;
}
int main(){
    int iter;
    cin >> iter;
    while(iter--)solve();
    return 0;
}