soj2757拓扑排序.cpp

一些ACM题目的解答,主要是soj和poj的

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

vector<int> list[10001];

struct point
{
    int a;
    int count;
    point(int x,int y)
    {
        a=x;
        count=y;
    }
};

int main(void)
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        int i;
        for(i=1;i<=n;i++)
            list[i].clear();
        bool flag=true;
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==b)
                flag=false;
            list[b].push_back(a);
        }
        if(!flag)
        {
            printf("Poor Xed\n");continue;
        }
        int indegree[10001]={0};
        int v1,v2;
        for(v1=1;v1<=n;v1++)
        {
            for(v2=0;v2<list[v1].size();v2++)
            {
                indegree[list[v1][v2]]++;
            }
        }
        queue<point> topsort;
        for(v1=1;v1<=n;v1++)
        {
            if(indegree[v1]==0)
            {
                topsort.push(point(v1,0));
            }
        }
        int sum=0,dian=0;
        while(!topsort.empty())
        {
            point x = topsort.front();
            topsort.pop();
            dian++;
            int v2;
            for(v2=0;v2<list[x.a].size();v2++)
            {
                if(--indegree[list[x.a][v2]]==0)
                {
                    topsort.push(point(list[x.a][v2],x.count+1));
                    sum+=x.count+1;
                }
            }
        }
        if(dian<n)
        {
            printf("Poor Xed\n");
        }
        else
        {
            printf("%d\n",sum+n*100);
        }
    }
    return 0;
}