特殊数据

1
4
A B
C D
D E
E C

非连通图，A 和 B 可以分开，但 CDE 无法分开。

C=1 D=0 E=1 C=0，矛盾

如果只从 A 开始，则不会遍历到 CDE 三个点，所以应对所有未染色的点进行 dfs。

AC

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<string, int> color;             //可以根据名字快速找到颜色
map<string, vector<string> > edges; //可以根据名字快速找到敌对的人，也就是边

bool dfs(string s, int c) {
    color[s] = c;
    for (int i = 0; i < edges[s].size(); ++i) {
        string v = edges[s][i];
        if (color[v] == c) return false;                //同色不合法
        if (color[v] == 0 && !dfs(v, -c)) return false; //无色时染成反色也不合法
    }
    return true;
}

int main() {
    int t, m, tag = 1;
    cin >> t;
    while (t--) {
        //清空，以便下一个情况
        color.clear();
        edges.clear();

        cin >> m;
        while (m--) {
            string u, v;
            cin >> u >> v;
            color[u] = 0;
            color[v] = 0;
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        //遍历所有名字，因为可能是非连通图
        int valid = 1;
        for (map<string, vector<string> >::iterator ite = edges.begin(); ite != edges.end(); ++ite) {
            string s = ite->first;
            //没有染色时进入 dfs 进行染色，如果不合法，则直接退出
            if (color[s] == 0 && !dfs(s, 1)) {
                valid = 0;
                break;
            }
        }
        if (valid)
            printf("Case #%d: Yes\n", tag);
        else
            printf("Case #%d: No\n", tag);
        tag++;
    }
    return 0;
}