洛谷OJ – P1347 排序（拓扑排序）

题目描述：

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列A,B,C,D 表示A

输入输出格式

输入格式：

第一行有两个整数n,m，n表示需要排序的元素数量，2<=n<=26，第1到n个元素将用大写的A,B,C,D….表示。m表示将给出的形如A

接下来有m行，每行有3个字符，分别为一个大写字母，一个<符号，一个大写字母，表示两个元素之间的关系。

输出格式：

若根据前x个关系即可确定这n个元素的顺序yyy..y（如ABC），输出

Sorted sequence determined after xxx relations: yyy…y.

若根据前x个关系即发现存在矛盾（如A

Inconsistency found after 2 relations.

若根据这m个关系无法确定这n个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定n个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

输入输出样例

1:
4 6
A

1:
Sorted sequence determined after 4 relations: ABCD.
2:
Inconsistency found after 2 relations.
3:
Sorted sequence cannot be determined.

题目思路：

每输入一条边进行一定判断，首先判断是否存在环，然后判断是否所有的结点都已出现，如果结点都出现，并且无环，那么找到入度为0的结点开始深搜，如果能遍历输出拓扑排序后的结果。如果不能遍历完，说明所有的结点并没有全部连通。继续下一步。

题目代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;


vector G[30];
int out[30], in[30];
int n, m, t, tot = 0;
int exist[30], topo[30];
int vis[30];
string s;
// 判断是否存在环 
bool dfs(int x){
    vis[x] = -1;
    for(int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        if(vis[y] == -1){
            return true;
        }
        // **  
        if(vis[y] == 0 && dfs(y))return true;
    }
    vis[x] = 1;
    return false;
}

void dfs2(int cur,int x, int cnt){    
    topo[cur] = x;
    if(cur == n-1){
        printf("Sorted sequence determined after %d relations: ",cnt);
        for(int i = 0; i < n; i++){
            printf("%c",topo[i]+'A'-1);
        }    
        printf(".\n");    
        exit(0);
    }
    for(int i = 0; i < G[x].size(); i++){

        dfs2(cur+1,G[x][i], cnt);
    }
}

void search(int i){    
     // 判环 
    for(int j = 1; j <= n; j++){
        if(exist[j]){
            memset(vis, 0, sizeof(vis));
            if(dfs(j)){
                printf("Inconsistency found after %d relations.\n",i);
                exit(0);
            }
        }
    }
    
     // 无环 
    if(tot == n){        
        
        for(int j = 1; j <= n; j++){
            if(!in[j]){
                dfs2(0,j,i);
            }
        }
                    
    }    
}

int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d %d", &n, &m);
    memset(exist, 0, sizeof(exist));
    memset(out, 0, sizeof(out));
    memset(in, 0, sizeof(in));
    
    for(int i = 1; i <= m; i++){
        cin>>s;
        int a = s[0] - 'A' + 1;
        int b = s[2] - 'A' + 1;
        out[a] ++; in[b]++; 
        if(!exist[a]) tot++;
        if(!exist[b]) tot++;
        exist[a] = exist[b] = 1;
        G[a].push_back(b); 
        search(i);        
    }
    printf("Sorted sequence cannot be determined.\n");
    return 0;
}