每接受一組關(guān)系，用Floyd算法計(jì)算傳遞閉包，
判斷是否有矛盾：if(adj[i][j]&&adj[j][i])isInconsitent=true;
判斷是否有關(guān)系未確定：if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;
如果沒(méi)有矛盾，所以關(guān)系確定，則說(shuō)明已經(jīng)sort好了，用dfs拓?fù)渑判蜉敵黾纯伞?br>
然后把未接受的數(shù)據(jù)接受完，剛開(kāi)始直接跳出了。
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
bool adj[27][27]; int n,m;
bool visit[27],isInconsitent=false,issorted=true;
vector<int>vec;
void Floyd()
{
int i,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
adj[i][j]= (adj[i][j]||adj[i][k]&&adj[k][j]);
}
void check()
{
isInconsitent=false,issorted=true;
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(adj[i][j]&&adj[j][i])isInconsitent=true;
if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;
}
}
void dfs(int i)
{
visit[i]=true;
for(int j=1; j<=n; j++)
if(!visit[j]&&adj[i][j])
dfs(j);
vec.push_back(i);
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0)break;
memset(adj,0,sizeof adj);
bool print=false;
int i,j;
char pre,last,less;
for(i=1; i<=m; i++)
{
cin>>pre>>less>>last;
adj[int(pre-'A'+1)][int(last-'A'+1)]=true;
Floyd();
check();
if(isInconsitent)
{
cout<<"Inconsistency found after "<<i<<" relations."<<endl;
print =true; break;
}
if(issorted)
{
cout<<"Sorted sequence determined after "<<i<<" relations: ";
vec.clear();
memset(visit,0,sizeof visit);
for(int t=1; t<=n; t++)
if(!visit[t])dfs(t);
while(vec.size())
{
cout<<char(vec[vec.size()-1]+'A'-1);
vec.pop_back();
}
cout<<'.'<<endl;
print=true; break;
}
}
if(print==false)cout<<"Sorted sequence cannot be determined."<<endl;
//accept the data left
for(j=i+1; j<=m; j++)
cin>>pre>>less>>last;
}
return 0;
}