hdu1811 拓扑细节

很好的一个拓扑排序。一不小心就wa。。。

对于a>b，连一条a到b的边，b>a就连一条b到a的边。a=b 就用并查集处理，这个地方很容易出错。解决的方法有很多种，我是通过vector，使得多个点所连向和被连上的边都集中到汇点上。最后拓扑排序，如果queue里面同时有2个入读为0的点，一定不完整。用拓扑排序也可以判断是否冲突。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5; 
int fa[maxn],n,m,in[maxn],vis[maxn];
char ss[5];
vector<int> e[maxn];
int find(int x){
	return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void unit(int x,int y){
	x=find(x); 
	y=find(y);
	if(x==y) return;
	fa[x]=y;
	e[y].insert(e[y].end(),e[x].begin(),e[x].end());
	e[x].clear();
	in[y]+=in[x];
	in[x]=0;
}
int tuopu(){
	queue<int> q;
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++){
		int x=find(i);
		if(vis[x]) continue;
		vis[x]=1;
		if(in[x]==0)q.push(x);
	}
	bool than2=false;
	memset(vis,0,sizeof(vis)); 
	while(!q.empty()){
		if(q.size()>=2) than2=true;
		int x=q.front();
		q.pop();
		vis[x]=1;
		vector<int>::iterator it;
		for(it=e[x].begin();it!=e[x].end();it++){
			int y=find(*it);
			if(find(x)==find(y)) return 1;
			in[y]--;
			if(!in[y]) q.push(y);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[find(i)]||in[i]) return 1;
	}
	if(than2) return 2;
	else return 3;
}
int main()
{
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++){
			fa[i]=i;
			in[i]=0;
			e[i].clear();
			memset(vis,0,sizeof(vis));
		}
		int a,b;
		for(int i=1;i<=m;i++){
			scanf("%d%s%d",&a,ss,&b);
			a++,b++;
			if('='==ss[0]){
				unit(a,b);
			}else if('>'==ss[0]){
				e[a].push_back(b);
				in[b]++;
			}else{
				e[b].push_back(a);
				in[a]++;
			}
		}
		for(int i=1;i<=n;i++){
			int x=i,y; 
			y=fa[i]=find(i);
			if(x==y) continue;
			e[y].insert(e[y].end(),e[x].begin(),e[x].end());
			e[x].clear();
			in[y]+=in[x];
			in[x]=0;
		}
		int res=tuopu();
		if(1==res) printf("CONFLICT\n");
		else if(2==res) printf("UNCERTAIN\n");
		else printf("OK\n");		
	}
    return 0;
}