Cod sursa(job #1359839)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 25 februarie 2015 08:44:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX=100005;
vector <int> Gi[NMAX], Ge[NMAX];
int i, n, j, m, Ui[NMAX], Ue[NMAX], n1, n2, U[NMAX], nod, ok, k;

void DFSe(int nod)
{	int k=0;
	++Ue[nod];
	for (k=0; k<Ge[nod].size(); ++k)
		if (!Ue[Ge[nod][k]]) DFSe(Ge[nod][k]);
}

void DFSi(int nod)
{	int k=0;
	++Ui[nod];
	for (k=0; k<Gi[nod].size(); ++k)
		if (!Ui[Gi[nod][k]]) DFSi(Gi[nod][k]);
}

int main()
{	f>>n>>m;
	for (; m; --m)
	{	f>>i>>j;
		Ge[i].push_back(j);
		Gi[j].push_back(i);
	}
	nod=1;
	while (!ok)
	{	DFSe(nod);
		DFSi(nod);
		ok=1;
		++k;
		U[nod]=k;
		for (i=1; i<=n; ++i)
			if (!U[i])
			{	if (Ui[i] && Ue[i]) U[i]=k;
				else
				{	ok=0;
					nod=i;
				}
			}
	}
	g<<k<<'\n';
	for (i=1; i<=k; ++i)
	{	for (j=1; j<=n; ++j)
			if (U[j]==i) g<<j<<' ';
		g<<'\n';
	}
    return 0;
}