Cod sursa(job #374861)

Utilizator katakunaCazacu Alexandru katakuna Data 18 decembrie 2009 15:51:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
// Kosaraju
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 100010

int n, m, i, x, y, nr, N, j;
int S[Nmax];
char viz[Nmax];
vector <int> G[Nmax], T[Nmax], CTC[Nmax];

void citire () {
	
	FILE *f = fopen ("ctc.in", "r");
	
	fscanf (f, "%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		fscanf (f, "%d %d", &x, &y);
		G[x].push_back (y);
		T[y].push_back (x);
	}
	
	fclose (f);
}

void DFS1 (int nod) {
	
	int i; viz[nod] = 1; 
	for (i = 0; i < (int)G[nod].size(); i++)
		if (!viz[G[nod][i]]) DFS1 (G[nod][i]);
	
	S[++N] = nod;
}

void DFS2 (int nod) {
	
	viz[nod] = 0; CTC[nr].push_back (nod);
	int i;
	for (i = 0; i < (int)T[nod].size(); i++)
		if (viz[T[nod][i]]) DFS2 (T[nod][i]);
}

void kosaraju () {
	
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS1 (i);
	
	for (; N; N--)
		if (viz[S[N]])
			nr++, DFS2 (S[N]);
}

void afisare () {
	
	FILE *g = fopen ("ctc.out", "w");
	
	fprintf (g, "%d\n", nr);
	for (i = 1; i <= nr; i++) {
		for (j = 0; j < (int)CTC[i].size(); j++)
			fprintf (g, "%d ", CTC[i][j]);
		
		fprintf (g, "\n");
	}
	
	fclose (g);
}

int main () {
	
	citire ();
	kosaraju ();
	afisare ();
	
	return 0;
}