拓扑排序 +Floyd（poj 1094）

题意：字母表前n个字母，有m组他们中的大小关系，判断n个字母是否构成唯一序列：

　　1.Sorted sequence determined after xxx relations: yyy...y.
2.Sorted sequence cannot be determined.
　　3.Inconsistency found after xxx relations.

思路：判断环好判断，但是判断是否唯一就搞不懂了，后来看了下别人的，

　　　　用的是Floyd传递闭包：如果能构成唯一序列，则定点1~n，必定分布着0~n-1的入度，

　　　　才能保证0个入度的定点排在第一位，1个入度的地点排在第2位，以此类推。

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 100

const double PI = acos(-1.0);

typedef long long LL ;

int topo[N],t;

int G[N][N];

int n,m,flag,pos,i,num;

char s[N];

char output[N];

int Floyd(){

    int i, j, k;

    for(i = ; i<n ;i++)

        for(k = ; k<n; k++)

            for(j = ; j<n; j++)

                if(G[k][i] && G[i][j])

                    G[k][j] = ;

    for(i = ; i< n; i++){

        if(G[i][i] == )

            return ;

    }

    return ;

}

int Topsort(){

    int cou, ind, k ,i;

    int degree[N],used[N];

    num = ;

    zero(used);

    zero(degree);

    for(i = ; i< n ;i++)

        for(k =  ; k< n ;k++)

            if(G[i][k])

                degree[k]++;

        for(i = ; i< n; i++){

            cou = ;

            for(k = ; k< n ; k++)

            if(degree[k] ==  && !used[k]){

                output[num++] = k + 'A';

                used[k] = ;

                cou++;

                ind = k;

            }

            if(cou > ) return ;

            if(cou == ) return ;

            for(k = ; k < n;k++)

                if(G[ind][k]) degree[k]--;

        }

        output[num] = '\0';

        return ;

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(cin>>n>>m){

        if(n ==  && m == ) break;

        flag = ;

        zero(G);

        for(i = ;i < m; i++){

            scanf("%s",s);

            G[s[]-'A'][s[]-'A'] = ;

            if(flag != ) continue;

            flag = Floyd();

            if(flag == )

                pos = i;

            if(flag == )

                flag = Topsort();

            else continue;

            if(flag == )

                pos = i;

        }

        pos++;

        if(flag == ){

            printf("Sorted sequence determined after %d relations: %s.\n",pos,output);

            continue;

        }

        if(flag == ){

            printf("Inconsistency found after %d relations.\n",pos);

            continue;

        }

        printf("Sorted sequence cannot be determined.\n");

    }

    return ;

}

巴特西

拓扑排序 +Floyd（poj 1094）

最新文章

热门文章