題目大意：給出若干個形如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 閱讀(205)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論