acdream 1056 （黑白染色）

题意：给你一些关系，每个关系是两只马的名字，表示这两个马不能在一个分组里，问你能否将这些马分成两组。

黑白染色，相邻的点染不同颜色。bfs搞即可，水题。

/*
* this code is made by wangzhili
* Problem: 1056
* Verdict: Accepted
* Submission Date: 2014-08-08 19:58:16
* Time: 24MS
* Memory: 1872KB
*/
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
map<string, int>mp;
int mat[222][222], vis[222], num;
bool bfs(){
    queue<int>Q;
    memset(vis, -1, sizeof vis);
    Q.push(1), vis[1] = 0;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i = 1;i <= num;i ++){
            if(mat[u][i] && vis[i] == -1){
                vis[i] = vis[u] ^ 1;
                Q.push(i);
            }else if(vis[i] != -1 && mat[u][i]) {
                if(vis[i] == vis[u]) return false;
            }
        }
    }
    return true;
}
int main(){
    string str1, str2;
    int t, n, CASE(0);
    scanf("%d", &t);
    while(t--){
        int u, v;
        memset(mat, 0, sizeof mat);
        mp.clear(), num = 0;
        scanf("%d", &n);
        for(int i = 0;i < n;i ++){
            cin >> str1 >> str2;
            map<string, int>::iterator it = mp.find(str1);
            if(it == mp.end()) mp.insert(pair<string, int>(str1, ++num)), u = num;
            else u = it->second;
            it = mp.find(str2);
            if(it == mp.end())  mp.insert(pair<string, int>(str2, ++num)), v = num;
            else v = it->second;
            mat[u][v] = mat[v][u] =  1;
        }
        printf("Case #%d: ", ++CASE);
        if(bfs()) printf("Yes
");
        else printf("No
");
    }
    return 0;
}