21 拓扑排序

理论说明

本次我们主要苏里一下图论中的另一个经典问题--拓扑排序，并以该问题作为图论最后一个专题。

设有一个有向无环图DAG，对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U,A），在该序列中结点U都排序在结点V之前。满足该要求的结点序列，我们称为满足拓扑次序的序列。求这个序列的过程，被称为拓扑排序。

基本算法：

 将入度为0的结点放入队列
  while(队列不空) {
     x=队列头
     for(i in （与x相联的结点）) {
       结点i的入度减少1
       if(结点i的队列为0) 入队列
     }
  }
  return 最后一个结点是否已经放入队列

题目来源和说明

来自王道考研九度OJ

题目描述

ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless，some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.

输入说明

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0. TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.

输出说明

For each test case, print in one line the judgement of the messy relationship. If it is legal, output "YES", otherwise "NO".

样例展示

输入：
3 2
0 1
1 2
2 2
0 1
1 0
0 0

输出：
YES
NO

C++代码

这里给出两份代码，第一个是基于数组进行了模拟队列和链表

#include<iostream>
using namespace std;

const int N=1000;
int h[N],e[N],ne[N],idx;
int q[N];
int d[N];
int n,m;

void add(int a,int b) {
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool qsort() {
    int hh=0,tt=-1;
    for(int i=0;i<n;i++) {
        if(d[i]==0) q[++tt]=i;
    }
    while(hh<=tt) {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]) {
            int j=e[i];
            d[j]--;
            if(d[j]==0) q[++tt]=j;
        }
    }
    return tt==n-1;
}
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(n==0&&m==0) break;
        for(int i=0;i<n;i++) {
            h[i]=-1;
            d[i]=0;
        }
        for(int i=0;i<m;i++) {
            int a,b;
            cin>>a>>b;
            add(a,b);
            d[b]++;
        }
        if(qsort()) {
            puts("Yes");
        }
        else puts("NO");
    }
    return 0;
}

第二种是王道考研给出的解决方案，如下(这种方法更容易理解)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> edge[501]; // 邻接链表
queue<int> Q;

int main() {
    int inDegree[501];
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(n==0&&m==0) break;
        //初始化，入度为0，邻接链表为空
        for(int i=0;i<n;i++) {
            inDegree[i]=0;
            edge[i].clear();
        }
        //读入边，变化度，变化邻接链表
        while(m--) {
            int a,b;
            scanf("%d%d",&a,&b);
            inDegree[b]++;
            edge[a].push_back(b);
        }
        while(Q.empty()==false) Q.pop(); //弹出队列，清空上一组数据
        //入队入度为0的结点
        for(int i=0;i<n;i++) {
            if(inDegree[i]==0) Q.push(i);
        }
        int cnt=0;
        while(Q.empty()==false) {
            int nowP=Q.front(); //取队头
            Q.pop(); //弹出队头
            cnt++; //被确定的结点个数加1
            for(int i=0;i<edge[nowP].size();i++) {
                inDegree[edge[nowP][i]]--;
                if(inDegree[edge[nowP][i]]==0) {
                    Q.push(edge[nowP][i]);
                }
            }
        }
        if(cnt==n) puts("YES");
        else puts("NO");
    }
}

确定比赛名次

https://www.nowcoder.com/questionTerminal/a3a561d688264a8baa31b3edf2610641

C++代码

//这里因为每次**队列的时候需要按照大小进行排序，因此直接用了王道考研的模板换成了优先级队列，其他基本是不变的。但是这个题目耗费了我好长的时间，找了好长时间的bug，没想到是edge开的太小了，只开了500.改成520就对了。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=10000;
vector<int> edge[520];
priority_queue<int, vector<int>, greater<int>> Q; //小顶堆
int inDegree[N];
int n,m;
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=1;i<=n;i++) {
            inDegree[i]=0;
            edge[i].clear();
        }
        while(m--) {
            int a,b;
            scanf("%d%d",&a,&b);
            inDegree[b]++;
            edge[a].push_back(b);
        }
        while(Q.empty()==false) Q.pop();
        for(int i=1;i<=n;i++) {
            if(inDegree[i]==0) Q.push(i);
        }
        int cnt=1;
        while(Q.empty()==false) {
            int nowP=Q.top();
            Q.pop();
            if(cnt==n)
                cout<<nowP<<endl;
            else
                cout<<nowP<<" ";
            cnt++;
            for(int i=0;i<edge[nowP].size();i++) {
                inDegree[edge[nowP][i]]--;
                if(inDegree[edge[nowP][i]]==0) Q.push(edge[nowP][i]);
            }
        }
    }
}

产生冠军

C++代码