拓扑排序 (有向图嘞) | EVA'S WONDERLAND

排序的啰 ~ 那么这次按啥顺序排嘞？？？

按啥顺序排呢？

该排序满足这样的条件——对于图中的任意两个结点和，若存在一条有向边从指向，则在拓扑排序中一定出现在前面

悟悟悟

例1

Eva.oj 0006

给一个有向图，判断图中是否存在“环”。

Input Format

第一行两个整数和，代表图中的点数和边数，接些来行，每行两个整数，有一条边从号点指向号点。

Output Format

有环则输出 ”exist loop!“ ；否则第一行输出 “no loop!”，然后输出任意一个包含所有点的序列。

解1

采用邻接表的方式存图，数组 indeg[N] ，用来存每个点的入度，当入度为时，说明这个点已经没有前置的点了，把这个点放到队列里。每次从队列里出一个元素，代表这个点进入序列，所有这个点的出边指向的点的入度。seq 用来存储最后要被输出的序列，

int indeg[N];

vector <int> e[N], seq;

queue<int> q;

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main() {
	int n = rd(), m = rd();
	for (int i = 1, u, v; i <= m; ++i) {
		u = rd(); v = rd();
		++indeg[v]; e[u].push_back(v));
	}
 	for (int i = 1; i <= n; ++i)
		if (!deg[i]) q.push(i);
	while (!q.empty()) {
		int u = q.front();
		q.pop(); seq.push_back(u);
		for (auto v : e[u]) {
			—-deg[v];
			if (!deg[v]) q.push(v);
		}	
	}
	if (seq.size() < n) puts(“exist loop!”);
	else {
		puts(“no loop!”);
		for (auto u : seq) printf(“%d “, u);
	}	
	return 0;
}

例2

Eva.oj 0007

在一个有向图中，输出最长路径的长度，若图不连通，输出 “inf”。

Input Format

第一行两个整数和，代表图中的点数和边数，接些来行，每行两个整数，有一条边从号点指向号点。

Output Format

一个整数代表该图中的最长路径长度。若不连通输出 ”inf“。

解2

来 dp 吧！！！！

dp 就需要状态转移方程啰。f[i] 代表以号点为终点的路径的最长长度。则状态转移方程为 ; 为有出边指向号点的点的编号。

queue<int> q;

int indeg[N], f[N]; 

vector<int> a[N], seq;

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	int n = rd(), m = rd();
	for(int i = 1; i <= m; ++i){
		int u = rd(), v = rd();		
		++indeg[v];
		a[u].push_back(v);
	}
	for(int i = 1; i <= n; ++i){ 
		if(!indeg[i]){
			q.push(i);
			seq.push_back(i);
            f[i] = 0;
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto i : a[u]){
			—-indeg[i]; 
			f[i] = max(f[i], f[u] + 1);
			if(!indeg[i]){
				q.push(i);
				seq.push_back(i);
			}
		}
	}
	if(seq.size() < n) printf(“inf”);
	else{
		int Max = 0;
		for(int i = 1; i <= n; ++i) Max = max(Max, f[i]);
		printf(“%d”, Max);
	}
	return 0;
}

例3

Eva.oj 0008

给一个有向图，输出该图中不同路径的条数。不同路径定义须满足的条件如下：

长度不同
同样的长度存在不同的点

Input Format

第一行两个整数和，代表图中的点数和边数，接些来行，每行两个整数，有一条边从号点指向号点。

Output Format

一个整数代表该图中不同路径的长度。若不连通，输出 ”inf“。

注：一个点到自己也算一条路径

解3

状态转移方程为，因为每个点都需要 +1 ，所以我们将每个点的 f[i] 初值设为。

queue<int> q;

int indeg[N], f[N]; 

vector<int> a[N], seq;

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	int n = rd(), m = rd();
	for(int i = 1; i <= m; ++i){
		int u = rd(), v = rd();		
		++indeg[v];
		a[u].push_back(v);
	}
	for (int i = 1; i <= n; ++i) f[i] = 1;
	for(int i = 1; i <= n; ++i){ 
		if(!indeg[i]){
			q.push(i);
			seq.push_back(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto i : a[u]){
			—-indeg[i]; 
			f[i] += f[u];
			if(!indeg[i]){
				q.push(i);
				seq.push_back(i);
			}
		}
	}
	if(seq.size() < n) printf(“inf”);
	else{
		int ans = 0;
		for(int i = 1; i <= n; ++i) ans += f[i];
		printf(“%d”, ans);
	}
	return 0;
}

练练练

例1

最大食物链计数

https://www.luogu.com.cn/problem/P4017

解1

求食物链的条数。状态转移方程为，入度为的点初值为，其余点为。最后答案是，所有出度为的点的 f[i] 之和。

#include <bits/stdc++.h>
#define N 5007
#define mod 80112002
using namespace std;

int n, m;

long long Ans;

queue<int> q;

vector<int> a[N];

int indeg[N], f[N], outdeg[N];

int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v;
		cin >> u >> v;
		a[v].push_back(u);
		++indeg[u];
		++outdeg[v];
	}
	for(int i = 1; i <= n; ++i){
		if(!indeg[i]){
			f[i] = 1;
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto i : a[u]){
			--indeg[i];
			f[i] = (f[i] + f[u]) % mod;
			if(!indeg[i]){
				q.push(i);
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		if(!outdeg[i]) Ans = (Ans + f[i]) % mod;
	}
	cout << Ans << endl; 
	return 0;
}