Cod sursa(job #993471)

Utilizator cont_de_testeCont Teste cont_de_teste Data 3 septembrie 2013 21:47:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int MAX_N = 100100;
const int MAX_M = 200100;

int n, m;
vector<int> g[MAX_N], gt[MAX_N];

void read() {
	ifstream fin("ctc.in");
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y;
		fin >> x >> y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
}

bool vis[MAX_N];
stack<int> sk;

void topo_sort(const int &node) {
	vis[node] = true;
	for (vector<int>::iterator it = g[node].begin(); it != g[node].end(); ++it)
		if (!vis[*it])
			topo_sort(*it);
	sk.push(node);
}

int ctc[MAX_N], c = 0;

void dfs(const int &node) {
	ctc[node] = c;
	for (vector<int>::iterator it = gt[node].begin(); it != gt[node].end(); ++it)
		if (!ctc[*it])
			dfs(*it);
}

void make_ctc() {
	while (sk.size()) {
		int node = sk.top();
		sk.pop();
		if (!ctc[node]) {
			++c;
			dfs(node);
		}
	}
}

vector<int> soln[MAX_N];

void write() {
	ofstream fout("ctc.out");
	for (int i = 1; i <= n; ++i)
		soln[ctc[i]].push_back(i);
	fout << c << '\n';
	for (int i = 1; i <= c; ++i, fout << '\n')
		for (vector<int>::iterator it = soln[i].begin(); it != soln[i].end(); ++it)
			fout << *it << ' ';
}

int main() {
	read();
	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			topo_sort(i);
	make_ctc();
	write();
}