﻿ UVa 11294

UVa 11294

她清楚其它人的人际关系，问是否能安排座位使得两边都是n个人，且公主看不见有奸情的人同一时候在的对面。

1.建图，矛盾的点建立相应的边（与一直关系相反）。

2.利用Tarjan算法计算强连通分量，缩点；

3.推断是否有解（是否有夫妇在同一集合）；

4.假设成立，利用拓扑排序求出一组解。输出。

```#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

typedef struct enode
{
int 	point;
enode* 	next;
}edge;
edge*H1[204],*H2[204];
edge E1[40004],E2[40004];
int  e_size1,e_size2;

{
e_size1 = 0; e_size2 = 0;
memset( H1, 0, sizeof(H1) );
memset( H2, 0, sizeof(H2) );
memset( E1, 0, sizeof(E1) );
memset( E2, 0, sizeof(E2) );
}

{
E1[e_size1].point = b;
E1[e_size1].next = H1[a];
H1[a] = &E1[e_size1 ++];
}

{
E2[e_size2].point = b;
E2[e_size2].next = H2[a];
H2[a] = &E2[e_size2 ++];
}

int  s_id,times,top;
int  dfn[204],low[204],use[204],stk[204],oth[204],set[204];
void tarjan( int i, int j )
{
dfn[i] = low[i] = ++ times;
use[i] = 1;
stk[++ top] = i;
for ( edge* p = H1[i] ; p ; p = p->next ) {
if ( !dfn[p->point] ) {
tarjan(p->point, 0);
low[i] = min(low[i], low[p->point]);
}else if ( use[p->point] )
low[i] = min(low[i], dfn[p->point]);
}
if ( dfn[i] == low[i] ) {
s_id ++;
do {
j = stk[top --];
use[j] = 0;
set[j] = s_id;
}while ( j != i );
}
}

void dfs( int i )
{
for ( edge* p = H2[i] ; p ; p = p->next )
if ( !use[p->point] ) {
dfs(p->point);
use[i] = use[p->point];
use[oth[i]] = use[oth[p->point]];
}
use[i] = 1;
use[oth[i]] = 2;
}

void solve( int n )
{
//强连通分量
s_id = times = top = 0;
memset( dfn, 0, sizeof(dfn) );
memset( use, 0, sizeof(use) );
for ( int i = 0 ; i < 2*n ; ++ i )
if ( !dfn[i] )
tarjan(i, 0);

//无解推断
for ( int i = 0 ; i < n ; ++ i )
if ( set[i*2] == set[i*2+1] ) {
");
return;
}else {
oth[set[i*2]] = set[i*2+1];
oth[set[i*2+1]] = set[i*2];
}

//拓扑排序
times = 0;
memset( use, 0, sizeof(use) );
for ( int i = 0 ; i < 2*n ; ++ i )
for ( edge* p = H1[i] ; p ; p = p->next )
if ( set[p->point] != set[i] )
for ( int i = 1 ; i <= s_id ; ++ i )
if ( !use[i] )
dfs(i);

for ( int i = 1 ; i < n ; ++ i ) {
if ( i > 1 ) printf(" ");
if ( use[set[i*2]] == use[set[0]] )
printf("%dw",i);
else printf("%dh",i);
}
printf("
");
}

int main()
{
int  n,m,x,y;
char ch1,ch2;
while ( ~scanf("%d%d",&n,&m) && n ) {

for ( int i = 0 ; i < m ; ++ i ) {
scanf("%d%c %d%c",&x,&ch1,&y,&ch2);

x <<= 1; y <<= 1;
if ( ch1 == 'w' ) x ^= 1;
if ( ch2 == 'w' ) y ^= 1;