Cod sursa(job #1250473)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 28 octombrie 2014 10:17:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#define IN "ctc.in"
#define OUT "ctc.out"
#define DMAX 100001
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int n, m;
int post[DMAX];
int npost;
vector <int> g[DMAX];
vector <int> gt[DMAX];
int use[DMAX];

void dfs1(int);
void dfs2(int);
void citire();
void showtime();

int afis;
int numara, nr;

int main(int argc, const char * argv[])
{
	citire();
	showtime();
    return 0;
}

void showtime()
{
	int i;
	for (i=1; i<=n; ++i)
		if (!use[i])
			dfs1(i);
	//primul dfs gata si vectorul post-ordine
	for (i=0; i<=n; ++i) use[i]=0;
	//reinit
	for (i=n; i>0; --i)
		if (!use[post[i]])
		{
			dfs2(post[i]);
			++nr;
		}
	fout <<nr<<'\n';
	for (i=0; i<=n; ++i) use[i]=0;
	for (i=n, afis=1; i>0; --i)
		if (!use[post[i]])
		{
			dfs2(post[i]);
			fout <<'\n';
		}
}

void dfs2(int c)
{
	int i;
	use[c]=1;
	if (afis) {fout <<c<<' ';}
	for (i=0; i<gt[c].size(); ++i)
		if (!use[gt[c][i]])
			dfs2(gt[c][i]);
}

void dfs1(int c)
{
	int i;
	use[c]=1;
	for (i=0; i<g[c].size(); ++i)
		if (!use[g[c][i]])
			dfs1(g[c][i]);
	post[++npost]=c;
}

void citire()
{
	fin >>n>>m;
	
	int i, x, y;
	for (i=0; i<m; ++i)
	{
		fin >>x>>y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
}