POJ 1094 sorting it all out

Hello everyone , I meet you again , I'm the king of the whole stack .

link ：poj 1094

The question ： Given a series of relationships （ Only capital letters exist ）, Infer whether there is contradiction ,

Or unable to determine the relationship . Or be able to determine the only relationship

analysis ： Using topological sorting . But you need to sort while entering the relationship

contradiction ： Infer whether there is a ring

Determine the relationship ： Can find the unique topological order

Not sure about the relationship ： There is no ring , And after all the relationships are processed , The relationship is still uncertain

notes ： Suppose there is a contradiction , Then there is no need to infer the next relationship

#include<stdio.h>
#include<string.h>
int n,m,vis[30],rd[30],flag[30],map[30][30],cnt;
char t[30];
int tpsort()
{
    int i,j,k,num,mark=1;
    cnt=0;
    memset(vis,0,sizeof(vis)); // Mark whether to access 
    for(i=0;i<n;i++)
        if(flag[i]){
            num=0;
            for(j=0;j<n;j++)    // The calculated penetration is 0 The number of 
                if(flag[j]&&!rd[j]&&!vis[j])
                    num++;     
            if(num==0)  // If there is no penetration, it is 0 node , Then there are rings 
                return 0;
            if(num>1)   // If the degree of penetration is 0 Node of is greater than 1. It indicates that a unique topological relationship cannot be established 
                mark=0;
            for(j=0;j<n;j++){
                if(flag[j]&&!rd[j]&&!vis[j]){
                    t[cnt++]=j+'A';
                    vis[j]=1;
                    break;
                }
            }
            for(k=0;k<n;k++)
                if(map[j][k])
                    rd[k]--;
        }
    if(!mark)
        cnt=0;
    return 1;
}
int main()
{
    int i,j,mark,pos,r[30];
    char s[5];
    while(scanf("%d%d",&n,&m)!=EOF){
        if(m==0&&n==0)
            break;
        mark=1;
        memset(map,0,sizeof(map));
        memset(flag,0,sizeof(flag)); // Mark whether the element exists 
        memset(r,0,sizeof(r));
        for(i=1;i<=m;i++){
            scanf("%s",s);
            if(mark==1){
                flag[s[0]-'A']=flag[s[2]-'A']=1;
                if(s[1]=='>'){
                    map[s[2]-'A'][s[0]-'A']=1;  // Record the relationship of edges 
                    r[s[0]-'A']++;              // Record the degree of penetration 
                }
                else{
                    map[s[0]-'A'][s[2]-'A']=1;
                    r[s[2]-'A']++;
                }
                for(j=0;j<n;j++)
                    rd[j]=r[j];   // Auxiliary space . Prevent topology sorting from changing the degree of penetration in the process 
                mark=tpsort(); 
                if(!mark)   
                    pos=i;
                if(mark&&cnt==n){  // When there is no ring and the relationship is certain 
                    mark=2;
                    pos=i;
                    t[cnt]=0;  // Empty characters at the end of the character array 
                }
            }
        }
        if(mark==0)
            printf("Inconsistency found after %d relations.\n",pos);
        else if(mark==1)
            printf("Sorted sequence cannot be determined.\n");
        else if(mark==2)
            printf("Sorted sequence determined after %d relations: %s.\n",pos,t);
    }
    return 0;
}

Copy

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116980.html Link to the original text ：https://javaforall.cn