Cod sursa(job #580073)

Utilizator aloneForever Alone alone Data 12 aprilie 2011 18:34:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>

using namespace std;

#define NMAX 100050

bool viz[NMAX];
int S[NMAX], N, nr, n, m;
vector <int> G[NMAX], GT[NMAX], CTC[NMAX];

void dfs1 (int), dfs2 (int), kosaraju (), citire (), afisare ();

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

void dfs1 (int nod) {
	
	viz[nod] = 1;
	for (vector <int>::iterator it =  G[nod].begin (); it != G[nod].end (); it++)
		if (!viz[*it]) dfs1 (*it);
	
	S[++N] = nod;
}

void dfs2 (int nod) {
	
	viz[nod] = 0; CTC[nr].push_back (nod);
	for (vector <int>::iterator it =  GT[nod].begin (); it != GT[nod].end (); it++)
		if (viz[*it]) dfs2 (*it);
}
void kosaraju () {
	
	for (int i = 1; i <= n; i++)
		if (!viz[i]) dfs1 (i);
	
	for ( ; N > 0; N--)
		if (viz[ S[N] ]) {
			nr++;
			dfs2 (S[N]);
		}
}

void citire () {
	
	ifstream f ("ctc.in");
	
	int i, x, y;
	
	f >> n >> m;
	
	for (i = 1; i <= m; i++) {
		f >> x >> y;
		G[x].push_back (y);
		GT[y].push_back (x);
	}
	
	f.close ();
}

void afisare () {
	
	ofstream g ("ctc.out");
	
	g << nr << "\n";
	
	for (int i = 1; i <= nr; i++) {
		for (vector <int>::iterator it = CTC[i].begin (); it != CTC[i].end (); it++)
			g << *it << " ";
		g << "\n";
	}
}