C++

「拓扑排序」POJ-1094 Sorting It All Out

Sorting It All Out

题目传送门 https://vjudge.net/problem/POJ-1094

没改完的code

//topologial order
//存图记录 入度 出度 
//队列维护
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

int aa,bb,flag,n,m,solve;
char x[10];
int a,b,map[30][30],indg[30];
int ans[30],cnt;
queue<int>q;

void init(){
    aa=flag=solve=0;
    cin>>n>>m;
    for(int i=0; i<=30; i++) indg[i]=0;
}

void topo_ans(){
    for(int i=0; i<n; i++){
        int t=ans[i];
        cout<<(char)(t+'A'-1)<<" ";
    }
    cout<<endl;
}

void topo(){
    for(int i=1; i<=30; i++) ans[i]=0; cnt=0;
    while (!q.empty()) q.pop();

    for(int i=1; i<=n; i++)
        if(indg[i]==0)
            q.push(i);

    while(!q.empty()){
        int u=q.front();
        ans[cnt++]=u;
        q.pop();
        for(int i=1; i<=n; i++){
            if(map[u][i]){
                indg[i]--;
                if(indg[i]==0)    q.push(i);
            }
        }
    }



}

void judge_circular(){

}

int main(){
    while(1){
        init();
        if(n==0 && m==0) break;

        for(int i=1; i<=m; i++){
            aa++;
            cin>>x;
            a=x[0]-'A'+1;
            b=x[2]-'A'+1;
            if(map[a][b]==1) continue;
            map[a][b]=1;
            indg[b]++;
            judge_circular();
            if(flag) break;
            solve=1;
        }

        if(!flag) topo();

        if(solve==1){
            cout<<"Sorted sequence determined after "<<bb<<" relations: ";
            topo_ans();
        }
        if(solve==2){
            cout<<"Inconsistency found after "<<aa<<" relations."<<endl;            
        }
        if(solve==3){
            cout<<"Sorted sequence cannot be determined."<<endl;
        }

    }
    return 0;
}

/*

if(map[a][b]==1 && map[b][a]==1) {cout<<"Inconsistency found after "<<aa<<" relations."<<endl;flag=1;break;}

*/

拓扑排序模版

void topo(){
    for(int i=1; i<=30; i++) ans[i]=0; cnt=0;
    while (!q.empty()) q.pop();
    for(int i=1; i<=n; i++)
        if(indg[i]==0)
            q.push(i);
    while(!q.empty()){
        int u=q.front();
        ans[cnt++]=u;
        q.pop();
        for(int i=1; i<=n; i++){
            if(map[u][i]){
                indg[i]--;
                if(indg[i]==0)    q.push(i);
            }
        }
    }
}
分享到