拓扑序列

概念

拓扑序列遵循一个规则，在遍历图的时候必须保证一条有向边的起点排在终点的前面

举一个例子

提供的有向边为：1 -> 2 | 2 -> 3 | 1 -> 3满足条件

而1 - > 2 | 2 -> 3 | 3 -> 1就不满足条件

如何实现拓扑序列？

• 找到所有入度为0的点，将其放入到队列中
• 将这些点从队列中弹出，并且将这些点所指向的终点的点入度减1
• 最后判断这些点是否入度为0，如果为0重新放入到队列中，循环这三种情况

Step1：找到入度为0的点

for(int i = 1;i <= n;i++) {
		if(!in(i)) q.push(i);
}

Step2：使该点指向的终点入度减1

while(q.size()) {
		int fr = q.front();
		q.pop();
		for(int i = h[fr];~i;i = ne[i]) {
				int j = ne[i];
				in[j]--;
		}
}

Step3：检查入度为0，重新放入队列

while(q.size()) {
		int fr = q.front();
		q.pop();
		for(int i = h[fr];~i;i = ne[i]) {
				int j = ne[i];
				in[j]--;
				if(!in[j]) q.push(j);
		}
}

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[N],h[N],ne[N],idx;
queue<int> q;
int d[N],top[N];int n,m,cnt;
void add(int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++; 
}

bool topsort() {
    for(int i = 1;i <= n;i++) {
        if(!d[i]) q.push(i);
    }

    while(q.size()) {
        int t = q.front();
        top[cnt++] = t;
        q.pop();
        for(int i = h[t];i != -1;i = ne[i]) {
            int j = e[i];
            d[j]--;
            if(d[j] == 0) {
                q.push(j);
            }
        }
    }

    return cnt == n;
}


int main(){
    memset(h,-1,sizeof(h));
    int a,b;
    cin >> n >> m;
    while(m--) {
        cin >> a >> b;
        d[b]++;
        add(a,b);
    }
    
    if(!topsort()) {
        cout << -1 << endl;
    }else {
        for(int i = 0;i < n;i++) {
            cout << top[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}