Cod sursa(job #361666)

Utilizator digital_phreakMolache Andrei digital_phreak Data 6 noiembrie 2009 10:43:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;

vector<vector<int> > Ans;
vector<int> G[MAXN];
vector<int> GT[MAXN];
int vis[MAXN];
int postordine[MAXN],nr;
int N,M;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int read() {
	int x,y;
	int i;
	fin >> N >> M;
	for (i=0;i<M;++i) {
		fin >> x >> y;
		x--;y--;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

int DFS(int x) {
	int i;
	vis[x] = 1;
	for (i=0;i<G[x].size();++i) {
		if (!vis[G[x][i]]) DFS(G[x][i]);
	}
	postordine[nr++] = x;
}

int DFST(int x,int k) {
	int i;
	vis[x] = 0;Ans[k].push_back(x);
	for (i=0;i<GT[x].size();++i) {
		if (vis[GT[x][i]]) DFST(GT[x][i],k);
	}
}

int solve() {
	int i,nrc;
	nrc = 0;
	
	memset(vis,0,sizeof(vis));
	
	for (i=0;i<N;++i) {
		if (!vis[i]) DFS(i);
	}
	
	for (i=N-1;i>=0;--i) {
		if (vis[postordine[i]]) {
			Ans.push_back(vector<int>());
			DFST(postordine[i],nrc);
			nrc++;
		}
	}
}

int write() {
	int i,j;
	fout << Ans.size() << "\n";
	for (i=0;i<Ans.size();++i) {
		for (j=0;j<Ans[i].size();++j) fout << Ans[i][j] + 1 << " ";
		fout << "\n";
	}
}

int main() {
	
	read();
	solve();
	write();
	
	fin.close();
	fout.close();
	return 0;
}