poj 3648 Wedding

題意：

新郎新娘宴會，宴會上一共有 n 對夫婦，編号分别為 0 ~ n - 1，其中新郎新娘編号為 0，丈夫為 h，妻子為 w 。

宴會的長桌上，新郎新娘各坐一邊，兩邊人數各為 n。在所有人中，存在 m 對異常關系，現在要求，新娘對面的那一邊所有人之間不能存在異常關系，要求你求出新娘的這邊的坐的人。這裡的異常關系指偷情（男男、男女、女女）。

分析：

沖突關系，有異常關系的兩人不能同時存在，即 a && b == 0。（a 與 b 兩個可以選擇其中一人做新郎這一邊，也可以選擇都坐在新娘這一邊）

需要注意的是，新郎必須在，是以必須在圖中加一條 0 -> n 的邊。（證明請找度娘，謝謝）

此外，有一點很要命，輸入不要"%s%s"，測試資料中存在無空格輸入的現象，用“%d%c %d%c”吧，這個，我表示我畫了一個小時陷在這個坑裡，悲催呀。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 11000;
const int inf = 1000000000;
vector<int>edge[maxn];
int n, m;
int tmpdfn, dfn[maxn], low[maxn], inst[maxn], belong[maxn], st[maxn], top, scnt;
int opp[maxn], in[maxn], color[maxn];
vector<int>arc[maxn];
queue<int>q;
void tarjan( int u )
{
	int i, v, t, size;
	low[u] = dfn[u] = tmpdfn++;
	st[top++] = u;
	inst[u] = 1;
	size = edge[u].size();
	for( i = 0; i < size; i++ )
	{
		v = edge[u][i];
		if( dfn[v] == -1 )
		{
			tarjan( v );
			low[u] = min( low[u], low[v] );
		}
		else if( inst[v] )low[u] = min( low[u], dfn[v] );
	}
	if( dfn[u] == low[u] )
	{
		do{ belong[t = st[--top]] = scnt; inst[t] = 0; }while( t != u );
		scnt++;
	}
}
bool SCC()
{
	int i;
	top = 0;
	tmpdfn = scnt = 1;
	memset( dfn, -1, sizeof(dfn) );
	memset( inst, 0, sizeof(inst) );
	for( i = 1; i <= n * 2; i++ )if( dfn[i] == -1 )tarjan( i );
	for( i = 1; i <= n; i++ )if( belong[i] == belong[i + n] )return false;
	return true;
}
void rebuild()
{
	memset( in, 0, sizeof(in) );
	int u, v, i, size;
	for( i = 1; i <= n * 2; i++ )arc[i].clear();
	for( u = 1; u <= n * 2; u++ )
	{
		size = edge[u].size();
		for( i = 0; i < size; i++ )
		{
			v = edge[u][i];
			if( belong[u] != belong[v] )
			{
				arc[belong[v]].push_back( belong[u] );
				in[belong[u]]++;
			}
		}
	}
}
void topusort()
{
	int i, j, u, v, size;
	while( !q.empty() )q.pop();
	memset( color, 0, sizeof(color) );
	for( i = 1; i < scnt; i++ )if( !in[i] )
		q.push( i );
	while( !q.empty() )
	{
		u = q.front();	q.pop();
		if( !color[u] )color[u] = 1, color[opp[u]] = 2;
		size = arc[u].size();
		for( i = 0; i < size; i++ )
		{	
			v = arc[u][i];
			in[v]--;
			if( !in[v] )q.push( v );
		}
	}
}
int main()
{
	int i, j, a, b, aa, bb;
	char s1, s2;
	while( ~scanf( "%d%d", &n, &m ), n + m )
	{
		for( i = 1; i <= n * 2; i++ )edge[i].clear();
		while( m-- )
		{
			scanf( "%d%c %d%c", &a, &s1, &b, &s2 );	// %s%s 輸入有誤，案例中輸入無空格
			a++;	b++;
			aa = s1 == 'w' ? 0 : 1;
			bb = s2 == 'w' ? 0 : 1;
			edge[a + aa * n].push_back( b + (!bb) * n );
			edge[b + bb * n].push_back( a + (!aa) * n );
		}
		edge[1].push_back( 1 + n );
		if( SCC() )
		{
			for( i = 1; i <= n; i++ )
			{
				opp[belong[i]] = belong[i + n];
				opp[belong[i + n]] = belong[i];
			}
			rebuild();
			topusort();
			for( i = 2; i <= n; i++ )
				if( color[belong[i]] == color[belong[1]] )printf( "%dw ", i - 1 );
				else printf( "%dh ", i - 1 );
			puts("");
		}
		else
			puts( "bad luck" );
	}
	return 0;
}
//1h 2w 3w 4h 5w 6w 7h 8w 9h