Cod sursa(job #775377)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 7 august 2012 22:28:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<vector>
#define NMAX 100010

using namespace std;

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

int n, m, ctc, nr, vz[NMAX], vzt[NMAX], po[NMAX];
vector<int> a[NMAX], at[NMAX], b[NMAX];

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 DFS(int nod)
{
	int v, i, lg;
	vz[nod]=nr; lg=a[nod].size();
	for (i=0; i<lg; ++i)
	{
		v=a[nod][i];
		if (!vz[v]) DFS(v);
	}
	po[++po[0]]=nod;
}

void DFSt(int nod)
{
	vector<int>::iterator it;	
	if (vz[nod]==nr)
	{
		vzt[nod]=nr; b[ctc].push_back(nod);
		for (it=at[nod].begin(); it!=at[nod].end(); ++it)
			if (!vzt[*it]) DFSt(*it);
	}
}

void Solve()
{
	int nod, i;
	for (nod=1; nod<=n; ++nod)
		if (!vz[nod])
		{
			++nr;
			DFS(nod);
		}
	for (i=po[0]; i>0; --i)
	{
		nod=po[i]; 
		if (!vzt[nod]) 
		{
			nr=vz[nod];
			++ctc;
			DFSt(nod);
		}
	}
}

void Scrie()
{
	int i;
	vector<int>::iterator it;
	g<<ctc<<"\n";
	for (i=1; i<=ctc; ++i)
	{
		for (it=b[i].begin(); it!=b[i].end(); ++it) g<<*it<<" ";
		g<<"\n";
	}
}

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