拓扑排序

有向无环图称为拓扑图；拓扑图一定存在至少一个入度为零的点。

简单例题

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 -1。

#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
const int N = 1e5 + 10, M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
bool mystate[N];
int myq[N], dist[N];

void myadd(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs()
{
	int l = 0, r = -1;
	for (int i = 1; i <= n; i++)
	{
		if (!dist[i])
			myq[++r] = i;//先把入度为0的点全部放入队列
	}
	while (l <= r)
	{
		int cur_pos = myq[l++];
		for (int i = h[cur_pos]; i != -1; i = ne[i])
		{
			int j = e[i];
			dist[j]--;
			if (!dist[j])
				myq[++r] = j;
		}
	}
	return r + 1;
}

int main()
{
	memset(h, -1, sizeof(h));
	memset(mystate, 0, sizeof(mystate));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		myadd(a, b);
		dist[b]++;//点的入度进行记录
	}
	if (bfs() != n)
		printf("%d", -1);
	else
		for (int i = 1; i <= n; i++)
			printf("%d ", i);
	return 0;
}

另一系列题

LeetCode207.课程表

LeetCode210.课程表II

class Solution {
public:
    vector<int> res, e, ne, h, cnt;
    int idx, m;
    void myadd(int x, int y)
    {
        e[idx] = y, ne[idx] = h[x], h[x] = idx++;
    }
    bool topsort()
    {
        queue<int> myq;
        for(int i = 0; i < cnt.size(); ++i)
            if(!cnt[i]) res.push_back(i), myq.push(i);
        while(myq.size())
        {
            int t = myq.front();
            myq.pop();
            for(int i = h[t]; i != -1; i = ne[i])
            {
                --cnt[e[i]];
                if(!cnt[e[i]]) res.push_back(e[i]), myq.push(e[i]);
            }
        }
        return res.size() == cnt.size();
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        if(!numCourses || !prerequisites.size())
        {
            while(numCourses--) res.push_back(numCourses);
            return res;
        }
        idx = 1, m = prerequisites.size();
        e = ne = vector<int>(m + 1), h = vector<int>(numCourses, -1), cnt = vector<int>(numCourses, 0);
        for(int i = 0; i < m; ++i)
        {
            myadd(prerequisites[i][1], prerequisites[i][0]);
            ++cnt[prerequisites[i][0]];
        }
        if(topsort()) return res;
        return {};
    }
};