ACMclubソートシーケンスの決定

ソート・シーケンスの決定
時間制限:1 Sec
メモリ制限:32 MB
タイトルの説明
異なる値からなる昇順でソートされたシーケンスで、通常はオペレータより小さいものを使用して、要素を小さいものから大きいものに並べます.たとえば、シーケンスA、B、C、Dは、AがAのような形をしていることを示します.
入力
複数のテストデータのセットを入力します.各グループに入力される最初の行は、2つの正の整数nおよびmである.nはソート対象の個数を表し、2<=n<=26である.ソート・オブジェクトは、アルファベットから始まるn文字の大文字です.mはAの次のm行のように形を表し、各行に1つの関係を入力し、3つの文字で構成される:最初の大文字、記号「n=m=0のとき、入力が終了する.
しゅつりょく
入力グループごとに1行出力します.行は次の3つのいずれかになります:Sorted sequence determined after xxx relations:yyy...y.(xxx個の関係の後、ソートシーケンス:yyy...y)Sorted sequence cannot be determined.(ソート順を特定できない)inconsistency found after xxx relations.(xxx個の関係後、関係矛盾が発見された)解釈説明:xxxが関係を処理する場合、ソートシーケンスが形成されたか、関係矛盾が発見された場合の関係数を確定し、どの状況が先に現れたか、どの種類を出力する.yyy...yはソートの昇順シーケンスです.
サンプル入力

4 6
A

サンプル出力

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

介道問題かトポロジーソートの問題か、この問題の鍵はエッジを追加するたびに連通しているかどうか、輪になっているかどうか、あるいは理不尽な状況を判断することであり、他には特に注意すべき点はないと思います.やはりトポロジーソートのテンプレートです.

#include   
#include   
#include   
using namespace std;  
int N, M;  
const int MAXN = 27, MAXM = 1000;  
int g[MAXN][MAXN], in[MAXN],  ans[MAXN];  
int topoSort()  
{  
    int in1[MAXN];  
    for(int i = 0; i < N; i++)//         
	{
		in1[i] = in[i]; 
	} 
    for(int k = 0; k < N; k++)  //       
    {  
        int i = 0;  
        while(in1[i]!=0) 
        {  
            i++;  
            if(i >= N)  //        ，      
                return 2;   //  ，    
        }  
        ans[k] = i;  //   0   ，  r  
        in1[i]--;  //   -1 
        for(int j = 0; j < N; j++)  //            -1 
            if(g[i][j])  
                in1[j]--;  
    }  
    for(int i = 0; i < N-1; i++)  //      
    {  
        int ok = 0;   
        if(g[ans[i]][ans[i+1]])  
            ok = 1;  
        if(!ok)  
            return 1;   //          
    }  
    return 0;           //      
}  
int main()  
{   
    while(scanf("%d%d", &N, &M)!=EOF && !(!N&&!M))  
    {  
        memset(g, 0, sizeof(g));  
        memset(in, 0, sizeof(in));  
        char s[10];  
        int next = 0;  
        for(int i = 0; i < M; i++)  
        {  
            scanf("%s", s);  
            if(next)  
                continue;  
            int u = s[0] - 'A', v = s[2] - 'A';  //  A       
            g[u][v] = 1;  //     
            in[v]++;  //     +1 
            int r = topoSort();  
            if(r == 0)  
            {  
                printf("Sorted sequence determined after %d relations: ", i+1);  
                for(int j = 0; j < N; j++) 
				{
					printf("%c", ans[j]+'A');  
				}
                printf(".
");  
                next = 1;  
                continue;  
            }  
            else if(r == 1 && i == M-1)  
                printf("Sorted sequence cannot be determined.
");  
            else if(r == 2)  
            {  
                printf("Inconsistency found after %d relations.
", i+1);  
                next = 1;  
                continue;  
            }  
        }  
    }  
    return 0;  
}