Cod sursa(job #811581)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 12 noiembrie 2012 18:02:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int V = 100001;

int n, m, d;
int depth[V], low[V], in_stack[V];
vector<int> G[V];
vector<vector<int> > scc;
stack<int> stk;

void dfs(int u, int p = 0) {
	depth[u] = low[u] = d++;
	stk.push(u);
	in_stack[u] = true;
	for (int i = G[u].size() - 1; i >= 0; i--) {
		int v = G[u][i];
		if (depth[v] == -1) {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
		} else if (in_stack[v]) {
			low[u] = min(low[u], depth[v]);
		}
	}
	if (low[u] == depth[u]) {
		vector<int> c;
		do {
			c.push_back(stk.top());
			in_stack[stk.top()] = false;
			stk.pop();
		} while (c.back() != u);
		scc.push_back(c);
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	n = next_int();
	m = next_int();
	for (int i = 0; i < m; i++) {
		int u = next_int();
		int v = next_int();
		G[u].push_back(v);
	}
	memset(depth, -1, sizeof depth);
	for (int i = 1; i <= n; i++) {
		if (depth[i] == -1) {
			dfs(i);
		}
	}
	printf("%d\n", int(scc.size()));
	for (int i = scc.size() - 1; i >= 0; i--) {
		for (int j = scc[i].size() - 1; j >= 0; j--) {
			printf("%d ", scc[i][j]);
		}
		printf("\n");
	}
	return 0;
}