Problem
As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn’t about to spend his valuable time figuring out how to split the League members by himself. That what he’s got you — his loyal henchman — for.
Input
The first line of the input gives the number of test cases,T.Ttest cases follow. Each test case starts with a positive integerMon a line by itself — the number of troublesome pairs of League members. The nextMlines each contain a pair of names, separated by a single space.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "Yes" or "No", depending on whether the League members mentioned in the input can be split into two groups with neither of the groups containing a troublesome pair.
Limits
1 ≤T≤ 100.Each member name will consist of only letters and the underscore character.Names are case-sensitive.No pair will appear more than once in the same test case.Each pair will contain two distinct League members.
Small dataset
1 ≤M≤ 10.
Large dataset
1 ≤M≤ 100.
Sample
2 -sat直接i j^1 j^1 i建边即可
#define N 2100#define M 100005#define maxn 205#define MOD 1000000000000000007int st[N],sn,n2,T,num,n;char s1[N],s2[N];vector<int> p[N];map<string,int> mymap;bool vis[N];bool DFS(int x){if(vis[x^1]) return false;if(vis[x]) return true;vis[x] = true;st[sn++] = x;FI(p[x].size()){if(!DFS(p[x][i])) return false;}return true;}bool sat_2(){fill(vis,false);for(int i = 0;i<n2;i++){if(!vis[i] ){sn = 0;if(!DFS(i)){FJ(sn) vis[st[j]] = false;sn = 0;if(!DFS(i^1))return false;}}}return true;}void add_edge(int a,int b){//printf("%d %d\n",a,b);//printf("%d %d\n",b^1,a^1);p[a].push_back(b);p[b].push_back(a);p[b^1].push_back(a^1);p[a^1].push_back(b^1);}int main(){freopen("A-small-2-attempt0.in", "r", stdin);freopen("A-small-2-attempt0.out", "w", stdout);while(S(T)!=EOF){for(int tcase = 1;tcase<=T;tcase++){S(n);mymap.clear();FI(N) p[i].clear();num = 0;FI(n){SS(s1);SS(s2);int x1,x2;if(mymap.count(s1)) {x1 = mymap[s1];}else {mymap[s1] = num;x1 = num;num +=2;}if(mymap.count(s2)) {x2 = mymap[s2];}else {mymap[s2] = num;x2 = num;num +=2;}add_edge(x1,x2^1);}n2 = num;if(sat_2()){printf("Case #%d: Yes\n",tcase);}else {printf("Case #%d: No\n",tcase);}}}fclose(stdin);fclose(stdout);return 0;}
InputOutput
21Dead_Bowie Fake_Thomas_Jefferson3Dead_Bowie Fake_Thomas_JeffersonFake_Thomas_Jefferson Fury_LeikaFury_Leika Dead_BowieCase #1: YesCase #2: No
，所有的胜利，与征服自己的胜利比起来，都是微不足道
