拓扑排序板子

经过一晚上的不懈努力,创造出了一个很烂的拓扑排序的板子 

这是精简版

using ll = long long;
struct tsort {
	int n;
	std::vector<std::vector<int>>g, w;
	std::vector<int>r, c, dp,f;
	std::queue<int>q;
	tsort(int n_) {
		n = n_;
		g.resize(n + 1);
		w.resize(n + 1);
		r.resize(n + 1);
		c.resize(n + 1);
		f.resize(n + 1);
		dp.resize(n + 1);
	}
    void add(int x, int y, int v = 0) {
		//有向边
		g[x].push_back(y);
		//值
		w[x].push_back(v);
		//入度
		r[y]++;
		//出度
		c[x]++;
	}
	ll all(int x=0, ll M=0, int s=0) {
		ll ans = 0;
		if(s)q.push(s);
		else {
			for (int i = 1; i <= n; i++) {//
				if (x && i != x) {
					dp[i] = -1e9;
					if (r[i] == 0)q.push(i);
				}
				else if (M&&r[i] == 0) {
					q.push(i);
					f[i] = 1;
				}
			}
		}
		while (!q.empty()) {//
			int x = q.front();//
			q.pop();//
			for (int i = 0; i < g[x].size(); i++) {//
				int j = g[x][i];//
				if(M)f[j] = (f[j] + f[x]) % M;
				if(s)dp[j] = std::max(dp[j], dp[x] + w[x][i]);
				r[j]--;//
				if (r[j] == 0) {
					if (M&&c[j] == 0) {
						ans = (ans + f[j]) % M;
						continue;
					}
					q.push(j);//
				}
			}
		}
		return ans;
	}
};

int main() {
	
	int n, m;
	std::cin >> n >> m;
	tsort t(n);
	while (m--) {
		int x, y;
		std::cin >> x >> y;
		t.add(x, y);
	}
	std::cout << t.all(0, 80112002,0);
	return 0;
}

传入第一个参数用于去除其它重复的入度为0的路径,传入第三个参数,用于计算从该点到其它的点的最长路径,两者通常结合在一起使用,传入第二个参数,用于计算入度为0出度为0的路径有多少个,第二个参数是模数.其它两个参数要设为0

下面这个是不省略的版本

using ll = long long;
struct tsort {
	int n;
	std::vector<std::vector<int>>g, w;
	std::vector<int>r, c, dp,f;
	std::queue<int>q;
	tsort(int n_) {
		n = n_;
		g.resize(n + 1);
		w.resize(n + 1);
		r.resize(n + 1);
		c.resize(n + 1);
		f.resize(n + 1);
		dp.resize(n + 1);
	}
	void add(int x, int y, int v = 0) {
		//有向边
		g[x].push_back(y);
		//值
		w[x].push_back(v);
		//入度
		r[y]++;
		//出度
		c[x]++;
	}
	//固定起点,去重
	bool dedup(int x) {
		//如果起点入度不为0,返回false
		//if (r[x])return false;
		for (int i = 1; i <= n; i++) {//
			if (i != x) {
				dp[i] = -1e9;
				if (r[i] == 0)q.push(i);
			}
		}
		while (!q.empty()) {//
			int x = q.front();//
			q.pop();//
			for (int i = 0; i < g[x].size(); i++) {//
				int j = g[x][i];//
				r[j]--;//
				if (r[j] == 0)q.push(g[x][i]);//
			}
		}
		return true;
	}
	//计算所有入度为0,出度为0的路径,M是模数
	ll pathsum(ll M= 80112002) {
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			if (r[i] == 0) {
				q.push(i);
				f[i] = 1;
			}
		}
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < g[x].size(); i++) {
				int j = g[x][i];
				r[j]--;
				f[j] = (f[j] + f[x]) % M;
				if (r[j] == 0) {
					if (c[j] == 0) {
						ans = (ans + f[j]) % M;
						continue;
					}
					q.push(j);
				}
			}
		}
		return ans;
	}
	void work(int s) {
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			//该点所对应的所有路径
			for (int i = 0; i < g[x].size(); i++) {
				dp[g[x][i]] = std::max(dp[g[x][i]], dp[x] + w[x][i]);
				if (!--r[g[x][i]])q.push(g[x][i]);
			}
		}
	}
	
};

int main() {
	
	int n, m;
	std::cin >> n >> m;
	tsort t(n);
	while (m--) {
		int x, y;
		std::cin >> x >> y;
		t.add(x, y);
	}
	std::cout << t.all(0, 80112002,0);
	return 0;
}

这个板子就略显臃肿

当然,如果你只想计算一条合理的拓扑序列,你可以将所有参数设为0,且将入度为0的点放入答案即可.