POJ 1094Sorting It All Out（拓扑排序）

题目地址：http://poj.org/problem?id=1094

这个题改了一下午。。代码越改越挫。。凑活着看吧。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
int d[30], head[30], n, cnt, a[30], num, s, hash1[30], y;
struct node
{
    int u, v, w;
    int next;
} edge[100000];
void add(int u, int v, int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int tops()
{
    int i, j, flag=0, x, u, z=0;
    s=0;
    while(1)
    {
        x=0;
        for(j=1; j<=n; j++)
        {
            if(hash1[j]&&d[j]==0)
            {
                a[s]=j;
                u=j;
                d[j]--;
                x++;
                s++;
            }
        }
        if(x==0&&s==n)
        {
            if(z==0)
            flag=1;
            break;
        }
        if(x==0&&s<y)
        {
            flag=2;
            break;
        }
        if(x==0&&s==y)
        {
            break;
        }
        if(x>=1)
        {
            if(x>1)
                z=1;
            for(i=0; i<s; i++)
            {
                for(j=head[a[i]]; j!=-1; j=edge[j].next)
                {
                    if(edge[j].w==1)
                    {
                        edge[j].w--;
                        d[edge[j].v]--;
                    }
                }
            }
        }
    }
    return flag;
}
int main()
{
    int m, i, flag, k, b[1000], dd[1000], yy;
    char c1, c2, c;
    //freopen("1.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        cnt=0;
        num=0;
        flag=0;
        memset(hash1,0,sizeof(hash1));
        while(m--)
        {
            cnt=0;
            num++;
            getchar();
            scanf("%c%c%c",&c1,&c,&c2);
            //printf("--1%c %c\n",c1,c2);
            b[num-1]=c1-'A'+1;
            //printf("--2%c %c\n",c1,c2);
            dd[num-1]=c2-'A'+1;
            //printf("--3%c %c\n",c1,c2);
            memset(head,-1,sizeof(head));
            memset(d,0,sizeof(d));
            //printf("--4%c %c\n",c1,c2);
            for(i=0; i<num-1; i++)
            {
                d[dd[i]]++;
                add(b[i],dd[i],1);
            }
            d[c2-'A'+1]++;
            add(c1-'A'+1,c2-'A'+1,1);
            hash1[c1-'A'+1]++;
            hash1[c2-'A'+1]++;
            y=0;
            for(i=1; i<=n; i++)
            {
                if(hash1[i])
                {
                    y++;
                }
            }
            if(!flag)
            {
                yy=tops();
                if(yy==1)
                {
                    k=num;
                    flag=1;
                }
                else if(yy==2)
                {
                    k=num;
                    flag=2;
                }
            }
        }
        if(flag==0)
            printf("Sorted sequence cannot be determined.\n");
        else if(flag==1)
        {
            printf("Sorted sequence determined after %d relations: ",k);
            for(i=0; i<n; i++)
                printf("%c",a[i]+'A'-1);
            printf(".\n");
        }
        else
            printf("Inconsistency found after %d relations.\n",k);
    }
    return 0;
}