首页 > 代码库 > POJ1094拓扑排序

POJ1094拓扑排序

每次输入的时候 进行一次 拓扑排序。 拓扑排序时,每次查找入度为零的点只有一个,则此解为确定解。若找到确定解之后出现环(坑),继续输入,不管它。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int main(){    //freopen("in.txt","r",stdin);   // freopen("out.txt","w",stdout);    int n,m;char str[100];    int vis[100];int G[100][100];    int in[100],in1[100];    int topo[100];    while(cin>>n>>m,n||m){        memset(G,0,sizeof(G));        memset(in,0,sizeof(in));        int flag=1;int ans=0;int sign=0;int sum=0;int pos;        for(int t=0;t<m;t++){            cin>>str;int a=str[0]-‘A‘;int b=str[2]-‘A‘;            if(!G[a][b]) {                G[a][b]=1;in[b]++;            }            for(int i=0;i<n;i++)                in1[i]=in[i];            int sum=0;            memset(vis,0,sizeof(vis));            for(int i=0;i<n&&flag;i++){                int sign1;bool k=false;                for(int j=0;j<n;j++){                   // cout<<j<<" "<<vis[j]<<" "<<in1[j]<<endl;                    if(in1[j]==0&&!vis[j]){                        sign1=j;sum++;k=true;                    }                }              //  cout<<i<<" "<<k<<endl;                vis[sign1]=1;                if(!ans) topo[i]=sign1;                if(!k){                    flag=0;sign=t+1;                }                for(int j=0;j<n;j++){                    if(!vis[j]) if(G[sign1][j]) in1[j]--;                }                pos=i;            }            if(pos==n-1&&sum==n&&!ans){                ans=t+1;            }        }        if(ans){            printf("Sorted sequence determined after %d relations: ",ans);            for(int i=0;i<n;i++){                char c=topo[i]+‘A‘;                cout<<c;            }            cout<<‘.‘<<endl;        }        else{            if(sign){                printf("Inconsistency found after %d relations.\n",sign);            }            else                printf("Sorted sequence cannot be determined.\n");        }    }    return 0;}