Cod sursa(job #903614)

Utilizator vld7Campeanu Vlad vld7 Data 1 martie 2013 23:26:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int MAX_N = 100005;

int n, m, postordine[MAX_N], nrsol, nr;

bool used[MAX_N];
vector <int> G[MAX_N], GT[MAX_N], SOL[MAX_N];

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		f >> a >> b;
		G[a].push_back(b);
		GT[b].push_back(a);
	}
}

void dfs(int nod) {
	used[nod] = 1;
	
	for (int i = 0; i < G[nod].size(); i++)
		if (!used[G[nod][i]])
			dfs(G[nod][i]);
		
	postordine[++nr] = nod;
}

void dfsT(int nod) {
	used[nod] = 0;
	
	SOL[nrsol].push_back(nod);
	for (int i = 0; i < GT[nod].size(); i++) {
		int vecin = GT[nod][i];
		if (used[vecin])
			dfsT(vecin);
	}
}

void solve() {
	for (int i = 1; i <= n; i++)
		if (!used[i])
			dfs(i);
		
	for (int i = n; i >= 1; i--)
		if (used[postordine[i]]) {
			nrsol++;
			dfsT(postordine[i]);
		}
}

void write() {
	g << nrsol << '\n';
	
	for (int i = 1; i <= nrsol; i++) {
		for (int j = 0; j < SOL[i].size(); j++)
			g << SOL[i][j] << " ";
		g << '\n';
	}
}

int main() {
	read();
	solve();
	write();
	
	f.close();
	g.close();
	
	return 0;
}