Cod sursa(job #839568)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 21 decembrie 2012 23:31:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <stack>


const int maxn = 100010;
using namespace std;

vector <int> g[maxn], v[maxn];
stack <int> tmp;
int nr;
char visited[maxn], in_stack[maxn];
int dfn[maxn], low[maxn];
int ticket;
void _pop(int node) {
	
	int x;	
	do {
		x = tmp.top(); tmp.pop();
		v[nr].push_back(x) ;
		in_stack[node] = 0;	

	} while(x != node);
	++nr;
}

void tarjan(int node) {
	dfn[node] = low[node] = ticket;
	visited[node] = in_stack[node] = 1;
	tmp.push(node);
	ticket += 1;
	for(vector <int> :: iterator it = g[node].begin(); it != g[node].end(); ++it) {
		if(visited[*it] == 0) {
			tarjan(*it);
			low[node] = min(low[node], low[*it]);
		}
		else if(in_stack[*it])
			low[node] = min(low[node], dfn[*it]);
	}
	if(low[node] == dfn[node]) {
		//found a root of a strongly connected component
		_pop(node);
	}

}
int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	int n, m, x, y;

	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d\n", &x, &y);
		g[x].push_back(y);
	}
	for(int i = 1; i <= n; ++i)
		if(!visited[i]) tarjan(i);

	printf("%d\n", nr);
	for(int i = 0; i < nr; ++i) {
		for(vector <int> :: iterator it = v[i].begin();it != v[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
	return 0;
}