Cod sursa(job #1155340)

Utilizator harababurelPuscas Sergiu harababurel Data 26 martie 2014 20:38:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define nmax 100005
using namespace std;

int n, m, a, b, comps = 0;
bool seen[nmax];
vector <int> v[nmax], vt[nmax], comp[nmax];
stack <int> S;

void dfs(int x) {
	seen[x] = true;

	for(int i=0; i<int(v[x].size()); i++) if(!seen[v[x][i]]) dfs(v[x][i]);
	S.push(x);
}

void secondDfs(int x) {
	seen[x] = true;

	comp[comps].push_back(x);
	for(int i=0; i<int(vt[x].size()); i++) if(!seen[vt[x][i]]) secondDfs(vt[x][i]);
}

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

	f>>n>>m;
	for(int i=1; i<=m; i++) {
		f>>a>>b;

		v[a].push_back(b);
		vt[b].push_back(a);
	}

	for(int i=1; i<=n; i++) if(!seen[i]) dfs(i);
	memset(seen, 0, nmax*sizeof(bool));

	while(!S.empty()) {
		int x = S.top();
		S.pop();
		if(!seen[x]) {
			secondDfs(x);
			comps++;
		}
	}

	g<<comps<<"\n";
	for(int i=0; i<comps; i++) {
		for(int j=0; j<int(comp[i].size()); j++) g<<comp[i][j]<<" ";
		g<<"\n";
	}

	return 0;
}