Cod sursa(job #1598151)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 12 februarie 2016 17:29:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
//============================================================================
// Name        :
// Author      : Teodor Cotet
// Version     :
// Copyright   : Your copyright notice
// Description : Strong Components, Kosaraju in O in O(N + M) C++, Ansi-style
//============================================================================
#include <fstream>
#include <vector>
#include <iostream>
#include <cstring>
#include <stack>
#include <set>

using namespace std;

const int NMAX = 100000;
const int MMAX = 200000;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n; int m;

/*
 * constructors for vector:
 * v(int size)
 * v(int size, TYPE value)
 */

vector< vector<int> > g(NMAX  + 1, vector<int>(0));
vector< vector<int> > gTranspose(NMAX + 1, vector<int>(0));

stack<int> s;

vector< vector<int> > strongComp;

void read() {

	fin >> n >> m;

	for(int i = 0 ; i < m ; ++i) {

		int x; int y;
		fin >> x >> y;

		g[x].push_back(y);

		gTranspose[y].push_back(x);
	}
}

void dfs(int curent, vector< vector<int> >& g, bool visited[]) {

	visited[curent] = 1;
	for(vector<int>::iterator it = g[curent].begin(); it != g[curent].end(); ++it) {
		if(visited[*it] == 0)
			dfs(*it, g, visited);
	}

	s.push(curent);
}

void dfsComponents(int curent, vector < vector<int> >& gTranspose, bool visited[]) {

	visited[curent] = 1;
	strongComp[strongComp.size() - 1].push_back(curent);

	for(vector<int>::iterator it = gTranspose[curent].begin(); it != gTranspose[curent].end(); ++it)
		if(visited[*it] == 0)
			dfsComponents(*it, gTranspose, visited);

}

void getStrongConnected(vector< vector<int> >& g, vector< vector<int> >& gTranspose) {

	/* do a topological sort first */

	bool visited[NMAX + 1];

	memset(visited, 0, n + 1);

	for(int i = 1; i <= n ; ++i) {
		if(visited[i] == 0)
			dfs(i, g, visited);
	}

	/* if there is a node which "enters" in the first node from the topological sort, it
	 * means they are in the same strong connected component, so we make a dfs in the transpose graph
	 */


	memset(visited, 0, n + 1);

	while( s.empty() == false) {

		int node = s.top();
		s.pop();

		if(visited[node] == 0) {
			strongComp.push_back(vector<int>(0));
			dfsComponents(node, gTranspose, visited);
		}
	}

}


void solve() {

	getStrongConnected(g, gTranspose);

	fout << strongComp.size() << '\n';

	for(unsigned i = 0 ; i < strongComp.size(); ++i) {
		for(unsigned j = 0 ; j < strongComp[i].size(); ++j)
			fout << strongComp[i][j] << " ";
		fout << '\n';
	}
}

int main() {

	read();

	solve();

	return 0;
}