Cod sursa(job #623123)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 19 octombrie 2011 11:04:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#include<vector>
#define N 100010
using namespace std;

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

int n,m,ordine[N],nrc,nr;
vector<int> g[N],ctc[N],gt[N];
bool vizitat[N];

inline void df_final(const int &nod) {
	vector<int>::iterator i;

	vizitat[nod]=true;
	
	for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i])
		df_final(*i);

	ordine[++nr]=nod;
}

inline void df(const int &nod) {
	vector<int>::iterator i;

	vizitat[nod]=true;
	ctc[nrc].push_back(nod);

	for(i=gt[nod].begin();i!=gt[nod].end();++i) if(!vizitat[*i])
		df(*i);
}

int main() {
	int i,a,b;

	in >> n >> m;

	for(i=1;i<=m;++i) {
		in >> a >> b;

		g[a].push_back(b);
		gt[b].push_back(a);
	}

    for(i=1;i<=n;++i) if(!vizitat[i])
        df_final(i);

	for(i=1;i<=n;++i)
		vizitat[i]=false;

	for(i=n;i!=0;--i) if(!vizitat[ordine[i]]) {
		++nrc;
		df(ordine[i]);
	}

	out << nrc << "\n";

	vector<int>::iterator it;


	for(i=1;i<=nrc;++i) {

		for(it=ctc[i].begin();it!=ctc[i].end();++it)
			out << *it << " ";

		out << "\n";
	}

	return 0;
}