欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——模板复习7

程序员文章站 2022-03-23 11:05:00
...

这里只有模板,并不作讲解,仅为路过的各位做一个参考以及用做自己复习的资料,转载注明出处。

Tarjan模板

/*Copyright: Copyright (c) 2018
*Created on 2018-10-28  
*Author: 十甫
*Version 1.0 
*Title: tarjan
*Time: 9.5 mins but 1 big mistake
*/
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
const int size = 100005;

int head[size];
struct edge {
	int to, next;
} data[size];
inline void add_edge(int from, int to, int i) {
	data[i] = (edge) {to, head[from]};
	head[from] = i;
}

int belong[size], dfn[size], low[size];
stack <int> sta;

void dfs(int pos, int &ord) {
	sta.push(pos);
	dfn[pos] = low[pos] = ord;
	for(int i = head[pos];i;i = data[i].next) {
		int u = data[i].to;
		if(dfn[u]) {
			low[pos] = min(low[pos], dfn[u]);
		} else {
			dfs(u, ++ord);
		}
		low[pos] = min(low[pos], low[u]);
	}
	if(low[pos] == dfn[pos]) {
		belong[pos] = ++belong[0];
		while(sta.top() != pos) {
			belong[sta.top()] = belong[0];
			sta.pop();
		}
		sta.pop();
	}
}


void tarjan(int n) {
	for(int i = 1;i <= n;i++) {
		if(!dfn[i]) {
			int ord = 1;
			dfs(i, ord);
		}
	}
	for(int i = 1;i <= n;i++) {
		printf("%d ", belong[i]);
	}
	printf("\n");
	return;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= m;i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add_edge(a, b, i);
	}
	tarjan(n);
	return 0;
}