Cod sursa(job #633626)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 14 noiembrie 2011 11:46:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<vector>
#define NMAX 100010

using namespace std;

vector<int> A[NMAX], AT[NMAX], B[NMAX];
int n, m, nr=0, vz[NMAX], st[NMAX];

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

void Citeste()
{
	int i, x, y;
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		A[x].push_back(y);
		AT[y].push_back(x);
	}
}

void DFSt(int nod)
{
	vector<int> :: iterator it;
	vz[nod]=1;
	for (it=AT[nod].begin(); it!=AT[nod].end(); ++it)
		if (!vz[*it]) DFSt(*it);
	st[++nr]=nod;
}

void DFS(int nod)
{
	vector<int> :: iterator it;
	vz[nod]=0; B[nr].push_back(nod);
	for (it=A[nod].begin(); it!=A[nod].end(); ++it)
		if (vz[*it]) DFS(*it);
}

void Solve()
{
	int i;
	vector<int> :: iterator it;
	for (i=1; i<=n; ++i)
		if (!vz[i]) DFSt(i);
	nr=0;
	for (i=n; i>0; --i) 
		if (vz[st[i]]) ++nr, DFS(st[i]);
	g<<nr<<"\n";
	for (i=1; i<=nr; ++i)
	{
		for (it=B[i].begin(); it!=B[i].end(); ++it)
			g<<*it<<" ";
		g<<"\n";
	}
}

int main()
{
	Citeste();
	
	Solve();
	
	f.close();
	g.close();
	return 0;
}