文章

25

粉丝

0

获赞

0

访问

244698

头像
Tarjan求有向图连通分量
经验总结
发布于2020年4月17日 22:13
阅读数 8557

 


time = 1; dfn[N] = { 0 }, low[N] = { 0 };
void dfs(int x){
	stack.push(x);
	dfn[x] = low[x] = time++;
	for (int y = 0; y < n; v++){
		if (g[x][y]){
			if (dfn[y] == 0){
				dfs(y);
				low[x] = min(low[x], low[y]);
			}
		}
		else if (y in stack){
			low[x] = min(low[x], low[y]);
		}
	}
}
main(){
	for (int x = 0; x < n; x++){
		if (dfn[x] == 0){
			dfs(x);
		}
	}
}
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
const int M = 510;
int h[N], e[M], next_pos[M], idx;
int belong[N], stack_arr[N], stack_top, is_in_stack[N], dfn[N], low[N], bent_num, time;
int n, m;
void add(int a, int b){
	e[++idx] = b;
	next_pos[idx] = h[a];
	h[a] = idx;
}
void tarjan(int x){
	dfn[x] = low[x] = ++time;
	stack_arr[++stack_top] = x;
	is_in_stack[x] = 1;
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (!dfn[j]){
			tarjan(j);
			low[x] = min(low[x], low[j]);
		}
		else if (is_in_stack[j]){
			low[x] = min(low[x], dfn[j]);
		}
	}
	if (dfn[x] == low[x]){//出栈
		++bent_num;
		int j;
		do{
			j = stack_arr[stack_top--];
			is_in_stack[j] = 0;
			belong[j] = bent_num;
		} while (j != x);
	}
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		add(x, y);
	}
	
	for (int i = 1; i <= n; i++){
		if (!dfn[i]){
			tarjan(i);
		}
	}

	for (int i = 1; i <= n; i++){
		cout << belong[i] << " ";
	}
	cout << endl;
	cout << "------------------" << endl;
	cout << bent_num << endl;


	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发