Cod sursa(job #1193368)

Utilizator howsiweiHow Si Wei howsiwei Data 31 mai 2014 16:13:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define ech(It, A) for (__typeof(A.begin()) It = A.begin(); It != A.end(); ++It)

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int> > adjl;
vector<int> dfs_num;
vector<int> dfs_low;
vector<int> scc_num;
vector<vector<int> > scc;
stack<int> dfs_stack;
int dfs_cnt = 1;
int scc_cnt = 1;

void dfs(int u) {
	dfs_low[u] = dfs_num[u] = dfs_cnt++;
	dfs_stack.push(u);

	ech(it, adjl[u]) {
		if (scc_num[*it] != 0) continue;
		if (dfs_num[*it] != 0) {
			dfs_low[u] = min( dfs_low[u], dfs_low[*it] );
		}
		else {
			dfs(*it);
			dfs_low[u] = min( dfs_low[u], dfs_low[*it] );
		}
	}

	if (dfs_low[u] == dfs_num[u]) {
		while (dfs_stack.top() != u) {
			scc_num[dfs_stack.top()] = scc_cnt;
			dfs_stack.pop();
		}
		scc_num[dfs_stack.top()] = scc_cnt;
		dfs_stack.pop();
		scc_cnt++;
	}
}

void tarjan_scc() {
	dfs_num.resize(n+1);
	dfs_low.resize(n+1);
	scc_num.resize(n+1);

	for (int i = 1; i <= n; ++i) {
		if (scc_num[i] == 0) dfs(i);
	}

	scc.resize(scc_cnt--);
	for (int i = 1; i <= n; ++i) {
		scc[scc_num[i]].push_back(i);
	}
}

int main() {
	fin >> n >> m;
	adjl.resize(n+1);
	
	for (int i = 0; i < m; ++i) {
		int u, v;
		fin >> u >> v;
		adjl[u].push_back(v);
	}

	tarjan_scc();

	fout << scc_cnt << '\n';
	for (int i = 1; i <= scc_cnt; ++i) {
		ech(it, scc[i]) {
			fout << *it << ' ';
		}
		fout << '\n';
	}

	return 0;
}