拓扑排序_牛客博客

1. HDU - 1285

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

#include <iostream>
#include <string.h>
using namespace std;
#define ll long long
int a[510],b[510],g[510][510];
int in[510],ans[550];
int n,m;
void tuopu()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(g[i][j])
                in[j]++;
    }
    for(int i=1;i<=n;i++)
    {
        int k = 1;
        while(in[k] != 0)//寻找入度为0的点
            k++;
        ans[i] = k;
        in[k] = -1;
        for(int j=1;j<=n;j++)
        {
            if(g[k][j])
                in[j]--;
        }
    }
}
int main()
{
    int x,y;
    while(cin>>n>>m)
    {
        memset(in,0,sizeof(in));
        memset(g,0,sizeof(g));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            g[x][y] = 1;
        }
        tuopu();
        for(int i=1;i<=n;i++)
        {
            if(i != 1)
                cout<<" ";
            cout<<ans[i];
        }
        cout<<endl;
    }

    return 0;
}

2.HDU - 2094

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

#include <iostream>
#include <string.h>
#include <string>
#include <map>
using namespace std;

int n,k;
int g[1010][1010],in[1010];
map<string,int> mp;
void tuopu()
{
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(g[i][j])
                in[j]++;
        }
    }
    int cnt = 0;
    for(int i=1;i<=k;i++)
    {
        if(in[i] == 0){
            cnt++;
        }
    }
    if(cnt == 1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return ;
}
int main()
{
    string c1,c2;
    while(cin>>n && n)
    {
        memset(in,0,sizeof(in));
        memset(g,0,sizeof(g));
        k = 0;
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>c1>>c2;
            if(mp[c1] == 0)
                mp[c1] = ++k;
            if(mp[c2] == 0)
                mp[c2] = ++k;
            g[ mp[c1] ][ mp[c2] ] = 1;
        }
        tuopu();
    }
    return 0;
}

3.POJ - 2367

一个家族里，人物关系很复杂，现在要排序每个人的话语权，要求每个祖先的话语权都要比子孙的高，输出话语权从大到小的顺序

#include <iostream>
#include <cstdio>
#include <string.h>
#define ll long long
using namespace std;

int g[110][110],in[110],ans[110],a[110];
int n;
void tuopu()
{

    for(int i=1;i<=n;i++)
    {
        int k = 1;
        while(in[k] != 0)
            k++;
        ans[i] = k;
        in[k] = -1;
        for(int j=1;j<=n;j++)
        {
            if(g[k][j])
                in[j]--;
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    int k;
    for(int i=1;i<=n;i++)
    {
        while(scanf("%d",&k) && k != 0)
        {
            g[i][k] = 1;
            in[k]++;
        }
    }
    tuopu();
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

4.HDU - 3342

经典拓扑，有环则输出NO，没环输出YES

#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
int n,m,x,y;
int g[102][102],in[102];
int tuopu()
{
    int k = 0 ,i,j;
    while(k<n)
    {
        for(i=0;i<n;i++)
        {
            if(in[i] == 0)
            {
                in[i] = -1;
                k++;
                for(j=0;j<n;j++)
                {
                    if(g[i][j])
                        in[j]--;
                }
                break;
            }
        }
        if(i == n)
            return 0;
    }
    return 1;
}
int main()
{
    while(scanf("%d%d",&n,&m) != -1 && n)
    {
        memset(g,0,sizeof(g));
        memset(in,0,sizeof(in));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            if(g[x][y] == 0)
            {
                 g[x][y] = 1;
                in[y]++;
            }
        }
        if(tuopu() == 1){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

5.POJ - 2585

有9个窗口，每个窗口占4个格子，并且每个窗口的位置是固定的。如果重叠的话，在前面的窗口会覆盖另一种窗口，这9个窗口在4*4的矩阵里面，给出一种矩阵的格局。问这中格局是不是合法的

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
int g[20][20];
int in[20];
int a[4][2] = {0,0, 0,1, 1,0, 1,1};
int b[11][2] = {-1,-1, 0,0, 0,1, 0,2, 1,0, 1,1, 1,2, 2,0, 2,1, 2,2 };
int c[5][5];

int tuopu()
{
    int flag ;
    for(int i=1;i<=9;i++)
    {
        flag = 0;
        for(int j=1;j<=9;j++)
        {
            if(in[j] == 0)
            {
                flag = 1;
                in[j] = -1;
                for(int k=1;k<=9;k++)
                {
                    if(g[j][k])
                        in[k]--;
                }
                break;
            }
        }
        if(!flag)
            return 0;
    }
    return 1;
}
int main()
{
    char str[20];
    int x,y,s,k;
    while(scanf("%s",str))
    {
        if(strcmp(str,"ENDOFINPUT") == 0)
        {
            break;
        }
        memset(g,0,sizeof(g));
        memset(in,0,sizeof(in));
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                cin>>c[i][j];
        scanf("%s",str);

        for(int i=1;i<=9;i++)
        {
            for(int j=0;j<4;j++)
            {
                x = b[i][0] + a[j][0];
                y = b[i][1] + a[j][1];
                s = c[x][y];
                if(s != i && g[i][s] == 0)
                {
                    g[i][s] = 1;
                    in[s]++;
                }
            }
        }
        if(tuopu())
        {
            cout<<"THESE WINDOWS ARE CLEAN"<<endl;
        }
        else{
            cout<<"THESE WINDOWS ARE BROKEN"<<endl;
        }
    }
    return 0;
}

#include <iostream>#include <string.h>#include <cstdio>usingnamespacestd; int n,m,x,y; int g[102][102],in[102]; int tuopu() { int k = 0 ,i,j; while(k<n) { for(i=0;i<n;i++) { if(in[i] == 0) { in[i] = -1; k++; for(j=0;j<n;j++) { if(g[i][j]) in[j]--; } break; } } if(i == n) return0; } return1; } int main() { while(scanf("%d%d",&n,&m) != -1 && n) { memset(g,0,sizeof(g)); memset(in,0,sizeof(in)); for(int i=0;i<m;i++) { scanf("%d%d",&x,&y); if(g[x][y] == 0) { g[x][y] = 1; in[y]++; } } if(tuopu() == 1){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } return0; }