学步园

拓扑排序水题

有重边，在读数据的同时计算入度时要注意去重

#include<stdio.h>
#include<stack>
using namespace std;
int n,map[105][105],link[105];
int tuopusort()
{
    int j,i;
       for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(map[i][j]==1)
                link[j]++;
    stack<int>Q;
    for(i=0;i<n;i++)
    if(link[i]==0)
        Q.push(i);
    j=0;
    while(!Q.empty())
    {
        int u=Q.top();
        Q.pop();
        j++;
        for(i=0;i<n;i++)
        {
            if(map[u][i]==1)
            {
                    link[i]--;
                if(link[i]==0)
                    Q.push(i);
             }
        }
    }
    if(j==n)return 1;
    else return 0;
}

int main()
{
    int j,i,a,b,m;
    while(scanf("%d%d",&n,&m),n&&m)
    {
        memset(map,0,sizeof(map));
        memset(link,0,sizeof(link));
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
                map[a][b]=1;
        }
        j=tuopusort();
        if(j==0)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}