程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ACdream 1056 Bad Horse （種類並查集）

ACdream 1056 Bad Horse （種類並查集）

編輯：C++入門知識

ACdream 1056 Bad Horse （種類並查集）

Bad Horse

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) SubmitStatus

Problem Description

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 (1 ≤ T ≤ 100).

T test cases follow.

Each test case starts with a positive integer M (1 ≤ M ≤ 100) on a line by itself -- the number of troublesome pairs of League members.

The next M lines each contain a pair of names, separated by a single space.

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.

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.

Sample Input

2
1
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie

Sample Output

Case #1: Yes
Case #2: No

大致題意：據說這題是出自google挑戰賽吧，但是偶然在ACdream上見到。題目是講一個教派裡面有好多幫派，現在要將這些幫派劃分成兩個大幫派。其中題目中給出了好多組相互對立的幫派，讓你判斷這些幫派是否可以劃分為兩個大幫派。

解題思路：這裡用到了很常見的並查集，但是這裡有點小小的變化，就是要開兩個空間，就是每個並查集都開了一個額外的空間，這裡具體處理的時候是在200以後的空間裡再存有一下。

先用map把string映射到int（這裡用map將我們要進行編號操作的string（字符串）映射到int，是一個很方便的處理string問題的手段。），然後合並a和b+200，a+200和b，當a與b或a+200與b+200在同一集合時，就產生了矛盾。

網上也有大神講可以用二分圖匹配做，暫時還不懂，就附上網址，感興趣的自己看吧二分圖匹配詳解

AC代碼：

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 10001;

int f[maxn];
map m;

int find(int x){
	return x == f[x] ? x : f[x] = find(f[x]);
}

void unin(int x, int y){
	x = find(x);
	y = find(y);
	if(x != y){
		f[x] = y;
	}
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif

	int T, n;
	string a, b;
	scanf("%d", &T);
	int cnt = 0;
	for(int t=1; t<=T; t++){
		scanf("%d", &n);
		int flag = 1;

		for(int i=0; i> a >> b;
			if(!m[a])   m[a] = cnt++;
			if(!m[b])   m[b] = cnt++;
			if(find( m[a] ) == find( m[b] ) || find( m[a]+200 ) == find( m[b]+200 ) )       //產生矛盾的判斷
				flag = 0;
			else{
				unin(m[a], m[b]+200);
				unin(m[a]+200, m[b]);
			}
		}
		printf("Case #%d: %s\n", t, flag ? "Yes" : "No"); 
	}
	return 0;
}