Cod sursa(job #1170870)

Utilizator sorin2kSorin Nutu sorin2k Data 14 aprilie 2014 19:29:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

// Q = o coada in care adaug mereu la final; Q[0] = nr de elmente din coada.
vector<int> adj[100000], inv[100000], ctc[100000];
int n, m, Q[100001], viz[100000], comp;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void dfs_direct(int start) {
	viz[start] = 1;
	for(vector<int>::iterator it = adj[start].begin(); it != adj[start].end(); ++it) {
		if(viz[*it] == 0) {
			dfs_direct(*it);
		}
	}
	Q[++Q[0]] = start;
}

void dfs_invers(int start) {
	viz[start] = 1;
	ctc[comp-1].push_back(start);
	for(vector<int>::iterator it = inv[start].begin(); it != inv[start].end(); ++it) {
		if(viz[*it] == 0) {
			dfs_invers(*it);
		}
	}
}

int main() {
	int i, u, v;
	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		inv[v].push_back(u);
	}
	for(i = 0; i < n; i++) {
		if(viz[i] == 0) {
			dfs_direct(i);
		}
	}
	memset(viz, 0, n*sizeof(int));
	for(i = Q[0]; i > 0; i--) {
		if(viz[Q[i]] == 0) {
			comp++;
			dfs_invers(Q[i]);
		}
	}
	fout << comp << "\n";
	for(i = 0; i < comp; i++) {
		for(vector<int>::iterator it = ctc[i].begin(); it != ctc[i].end(); ++it) {
			fout << *it + 1 << " ";
		}
		fout << "\n";
	}
	return 0;
}