题目链接： ACdream 1056
题解： 其实就是让你判断是否是一个二分图。 随便做….BFS or dsu （并查集）。 我都写一个吧。
BFS代码：
/* * this code is made by LzyRapx * Problem: 1056 * Verdict: Accepted * Submission Date: 2017-06-06 22:53:47 * Time: 68MS * Memory: 1704KB */ #include <bits/stdc++.h> using namespace std; map<string,int>color; map<string,vector<string> >G; int bfs(string source) { string u,v; u=source; color[source] = 1; queue<string>q; q.push(source); while(!q.empty()) { u = q.front(); q.pop(); for(int i=0;i<G[u].size();i++) { v = G[u][i]; if(color[v] == -1 && color[u] != color[v]) { color[v] = 1-color[u]; q.push(v); } else if (color[v] == color[u]) { return 0; } } } return 1; } int main() { int cas=1,t; cin>>t; int n; string s1,s2; while(t--) { cin>>n; G.clear(); color.clear(); for(int i=1;i<=n;i++) { cin>>s1>>s2; G[s1].push_back(s2); G[s2].push_back(s1); color[s1]=color[s2]=-1; } printf("Case #%d: ",cas++); if(bfs(color.begin()->first)) { puts("Yes"); } else{ puts("No"); } } return 0; }DSU代码：
/* * this code is made by LzyRapx * Problem: 1056 * Verdict: Accepted * Submission Date: 2017-06-06 23:08:08 * Time: 36MS * Memory: 1684KB */ #include <bits/stdc++.h> using namespace std; map<string,int>color; int fa[456]; int getfather(int x) { return fa[x]==x?x:fa[x]=getfather(fa[x]); } void Merge(int a,int b) { int p1=getfather(a); int p2=getfather(b); fa[p1] = p2; } int main() { int cas=1,t; cin>>t; int n; string s1,s2; while(t--) { int flag = 1; color.clear(); int t = 1; cin>>n; n<<=1; for(int i=1;i<=n;i++)fa[i]=i; n>>=1; for(int i=1;i<=n;i++) { cin>>s1>>s2; if(flag==0)continue; if(color[s1]==0) color[s1] = t++; if(color[s2]==0) color[s2] = t++; if(getfather(color[s1]) != getfather(color[s2]) ) { Merge(color[s1],n+color[s2]); Merge(color[s1]+n,color[s2]); } else { flag = 0; } } printf("Case #%d: ",cas++); puts(flag?"Yes":"No"); } return 0; }