题目大意：给出若干个形如A<B的表达式，判断是否出现矛盾、是否能够确定唯一的一个序列。
根据A<B构造图，出现矛盾即是出现有向环；没有矛盾就进行拓扑排序。本题需要边构图边判断，在这过程中，图可能是不连通的，通过DFS判断有向环比较方便，而用顶点的度来判断序列是否唯一比较方便。
以下是我的代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(27);
int n,m,g[kMaxn][kMaxn],degree[kMaxn];
int used[kMaxn];
bool circle(int u)
{
used[u]=-1;
for(int i=1;i<=n;i++)
if(g[u][i])
{
if(used[i]==-1)
return true;
else if(used[i]==0 && circle(i))
return true;
}
used[u]=1;
return false;
}
bool toposort(string &ansstr)
{
int d[kMaxn];
ansstr.clear();
memcpy(d,degree,kMaxn*sizeof(int));
for(int i=1;i<=n;i++)
{
int now,cnt(0);
for(int j=1;j<=n;j++)
if(d[j]==0)
{
now=j;
cnt++;
}
if(cnt>1)
return false;
ansstr+=(char)(now+'A'-1);
d[now]=-1;
for(int j=1;j<=n;j++)
if(g[now][j])
d[j]--;
}
return (ansstr.size()==n);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
int anstype(-1),ansvalue;
string ansstr;
memset(g,0,kMaxn*kMaxn*sizeof(int));
memset(degree,0,kMaxn*sizeof(int));
for(int i=1;i<=m;i++)
{
string t;
cin>>t;
g[t[0]-'A'+1][t[2]-'A'+1]=1;
degree[t[2]-'A'+1]++;
memset(used,0,kMaxn*sizeof(int));
if(anstype==-1 && circle(t[0]-'A'+1))
{
anstype=3;
ansvalue=i;
}
if(anstype==-1 && toposort(ansstr))
{
anstype=1;
ansvalue=i;
}
}
if(anstype==3)
printf("Inconsistency found after %d relations.\n",ansvalue);
else if(anstype==1)
printf("Sorted sequence determined after %d relations: %s.\n",ansvalue,ansstr.c_str());
else
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
posted on 2011-05-27 15:18
lee1r 阅读(178)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论