Day5

拓扑排序

对于一个有向无环图，我们可以需要求一个特定的序列。

比如说一个很经典的例子，先修课程例子，必须先修完先修课程才能修本课。

graph LR
A((A)) --> B((B));
A --> C((C));
B --> D((D));
C --> D;

graph LR
B1((B)) --> D1((D));
C1((C)) --> D1;

graph LR;
D2((D));

很简单的一个排序就是ABCD或者ACBD。

那么怎么通过程序得到这个拓扑排序呢

我们需要知道图中的点有出度和入度，当一个点没有入度，我们就可以知道这个点没有先修课程，这个点就可以当作目前的第一个选择。

然后我们选择了这个点，那么我们就需要把这点以及所有从这点出去的线都删除。然后再进行后续操作。

由此我们可以写出拓扑排序的模板

HDU-3342

题意：问一个图是否有拓扑序列，点从0开始

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
int n,m;
struct egde{
    int nex,to;
}e[maxn<<1];
int in[maxn]; //入度
int intmp[maxn]; 
int seq[maxn]; //一种可能的拓扑序
int head[maxn],ecnt;
void init(){
    memset(head,-1,sizeof head);
    memset(in,0,sizeof in);
    ecnt=0;
}
void add(int from,int to){
    e[ecnt].nex=head[from];
    e[ecnt].to=to;
    head[from]=ecnt++;
    in[to]++;
}
int topo(){
    queue<int>q; //利用队列来进行存储seq序列
    for(int i=0; i<n; i++){
        intmp[i]=in[i];
        if(!intmp[i]) q.push(i);
    }
    bool ok=false;
    int num=0;
    while(!q.empty()){
        if(q.size()!=1) ok=true; //如果每次找点都有不止一个点符合入度为0,那么答案seq就不止一种
        int x=q.front();
        q.pop();
        seq[num++]=x;
        for(int i=head[x]; ~i; i=e[i].nex){ //链式前向星进行检索
            int son=e[i].to;
            intmp[son]--; //相当于删除边的操作,因为删除边就相当于减少了连接的点的入度
            if(!intmp[son]) q.push(son);
        }
    }
    if(num < n) return -1; //没有拓扑序列
    if(ok) return 0; //存在不止一个拓扑序列,seq是其中一种拓扑序列
    return 1; //seq是唯一的拓扑序列
}
int main(){
    while(scanf("%d %d",&n,&m)&&n){
        init();
        for(int i=0; i<m; i++){
            int x,y;
            scanf("%d %d",&x,&y);
            add(x,y);
        }
        int tmp=topo();
        if(tmp != -1) puts("YES");
        else puts("NO");
    }
}