poj3678 Katu Puzzle

学习建图

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, hea[2005], cnt, scc, ind, dfn[2005], loo[2005], bel[2005];
int uu, vv, ww, sta[2005], din;
bool ins[2005];
char c[15];
struct Edge{
	int too, nxt;
}edge[4000005];
void add_edge(int fro, int too){
	edge[++cnt].nxt = hea[fro];
	edge[cnt].too = too;
	hea[fro] = cnt;
}
void tarjan(int u){
	sta[++din] = u;
	ins[u] = true;
	dfn[u] = loo[u] = ++ind;
	for(int i=hea[u]; i; i=edge[i].nxt){
		int t=edge[i].too;
		if(!dfn[t]){
			tarjan(t);
			loo[u] = min(loo[u], loo[t]);
		}
		else if(ins[t])	loo[u] = min(loo[u], dfn[t]);
	}
	int j;
	if(dfn[u]==loo[u]){
		scc++;
		do{
			j = sta[din--];
			ins[j] = false;
			bel[j] = scc;
		}while(dfn[j]!=loo[j]);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		scanf("%d %d %d", &uu, &vv, &ww);
		scanf("%s", c);
		uu *= 2; vv *= 2;
		if(c[0]=='A'){
			if(ww){
				add_edge(uu, vv); add_edge(vv, uu);
				add_edge(uu^1, uu); add_edge(vv^1, vv);//只要敢不选就让它矛盾
			}
			else
				add_edge(uu, vv^1), add_edge(vv, uu^1);
		}
		if(c[0]=='O'){
			if(ww)
				add_edge(uu^1, vv), add_edge(vv^1, uu);
			else{
				add_edge(uu, uu^1); add_edge(vv, vv^1);
				add_edge(uu^1, vv^1); add_edge(vv^1, uu^1);
			}
		}
		if(c[0]=='X'){
			if(ww){
				add_edge(uu, vv^1); add_edge(vv, uu^1);
				add_edge(vv^1, uu); add_edge(uu^1, vv);
			}
			else{
				add_edge(uu, vv); add_edge(vv, uu);
				add_edge(uu^1, vv^1); add_edge(vv^1, uu^1);
			}
		}
	}
	for(int i=0; i<n+n; i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=0; i<n+n; i+=2)
		if(bel[i]==bel[i^1]){
			printf("NO
");
			return 0;
		}
	printf("YES
");
	return 0;
}