Cod sursa(job #1038366)

Utilizator alex03mihaimihai alexandru alex03mihai Data 21 noiembrie 2013 13:44:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <vector>
#define NMAX 100005

using namespace std;

FILE * fin = fopen("ctc.in", "r");
FILE * fout = fopen("ctc.out", "w");

void citire();
void rezolvare();
void DFS(int);
void DFST(int);
void afisare();

vector <int> G[NMAX], GT[NMAX], C[NMAX];
int postordine[NMAX], viz[NMAX];
int n, m, componente, k = 0;
int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}

void citire()
{
	int i, a, b;
	fscanf(fin, "%d %d", &n, &m);
	for (i = 1; i <= m; i ++)
	{
		fscanf(fin, "%d %d", &a, &b);
		G[a].push_back(b);
		GT[b].push_back(a);
	}
}

void rezolvare()
{
	int i;
	for (i = 1; i <= n; i ++)
		if (viz[i] == 0)
			DFS(i);
	componente = 0;
	for (i = n; i > 0; i --)
		if (viz[postordine[i]] == 1)
		{
			componente ++;
			DFST(postordine[i]);
		}
}

void DFS(int x)
{
	int i;
	viz[x] = 1;
	for (i = 0; i < G[x].size(); i ++)
		if (viz[G[x][i]] == 0)
			DFS(G[x][i]);
	postordine[++k] = x;
}

void DFST(int x)
{
	int i;
	viz[x] = 0;
	for (i = 0; i < GT[x].size(); i ++)
		if (viz[GT[x][i]] == 1)
			DFST(GT[x][i]);
	C[componente].push_back(x);
}

void afisare()
{
	int i, j;
	fprintf(fout, "%d\n", componente);
	for (i = 1; i <= componente; i ++)
	{
		for (j = 0; j < C[i].size(); j ++)
			fprintf(fout, "%d ", C[i][j]);
		fprintf(fout, "\n");
	}
}