Cod sursa(job #1359853)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 25 februarie 2015 09:01:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;

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

vector <int> G[NMAX], Gt[NMAX], l[NMAX];
int i, j, k, n, m, x, y, st[NMAX], nr, nc;
bool U[NMAX];

void DF(int nod)
{	int k;
	U[nod]=1;
	for (k=0; k<G[nod].size(); ++k)
		if (!U[G[nod][k]])
			DF(G[nod][k]);
	st[++nr]=nod;
}

void DFt(int nod, int af)
{	int k;
	U[nod]=1;
	l[nc].push_back(nod);
	for (k=0; k<Gt[nod].size(); ++k)
		if (!U[Gt[nod][k]])
			DFt(Gt[nod][k], af);
}

int main()
{	f>>n>>m;
	for (; m; --m)
	{	f>>i>>j;
		G[i].push_back(j);
		Gt[j].push_back(i);
	}
	nr=nc=0;
	for (i=1; i<=n; ++i)
		if (!U[i]) DF(i);
	for (i=1; i<=n; ++i)
		U[i]=0;
	for (i=n; i>=1; --i)
		if (!U[st[i]])
		{	++nc;
		    DFt(st[i], 0);
		}
	g<<nc<<'\n';
	for (i=1; i<=nc; ++i)
    {   for (j=0; j<l[i].size(); ++j)
            g<<l[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}