Cod sursa(job #1686061)

Utilizator aimrdlAndrei mrdl aimrdl Data 12 aprilie 2016 00:40:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

int n, m;
vector< vector<int> > G;
vector< vector<int> > GT;
vector< vector<int> > sol;
stack <int> S;
bool visited[100005];

void read () {
	scanf("%d %d", &n, &m);

	G.resize(n + 1);
	GT.resize(m + 1);

	int x, y;
	for (int i = 0; i < m; ++i) {
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

void dfs (int i) {	
	visited[i] = true;

	vector<int>::iterator it;
	for (it = G[i].begin(); it != G[i].end(); ++it) {
		if (!visited[*it]) {
			dfs(*it);
		}
	}
	S.push(i);
}

void dfsT (int i) {
	visited[i] = true;
	sol[sol.size() - 1].push_back(i);

	vector<int>::iterator it;
	for (it = GT[i].begin(); it != GT[i].end(); ++it) {
		if (!visited[*it]) {
			dfsT(*it);
		}
	}
}

void kosaraju () {
	for (int i = 1; i <= n; ++i) {
		if (!visited[i]) dfs(i);
	}

	memset(visited, 0, sizeof(visited));
	while (!S.empty()) {
		int i = S.top();
		if (!visited[i]) {
			sol.push_back(vector<int> (0));
			dfsT(i);
		}
		S.pop();
	}
}

int main (void) {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	read();

	kosaraju();

	printf("%lu\n", sol.size());

	vector< vector<int> >::iterator it;
	for (it = sol.begin(); it != sol.end(); ++it) {
		vector<int>::iterator jt;
		for (jt = (*it).begin(); jt != (*it).end(); ++jt) {
			printf("%d ", *jt);
		}

		printf("\n");
	}

	return 0;
}