Cod sursa(job #1458398)

Utilizator glbglGeorgiana bgl glbgl Data 7 iulie 2015 14:13:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;


int N, M, count = 0;
stack<int> st;
vector< vector<int> > neigh;
vector< vector<int> > neighT;
vector< vector<int> > components;
vector<bool> visited;


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


void read(){

	in >> N >> M;

	visited.resize(N+1);
	for(int i = 0; i <= N; ++i){
		vector<int> v;
		vector<int> vT;
		vector<int> c;
		neigh.push_back(v);
		neighT.push_back(vT);
		components.push_back(c);
	}

	int x, y;

	for(int i = 0; i < M; ++i){
		in >> x >> y;
		neigh[x].push_back(y);
		neighT[y].push_back(x);
	}
}


void DFS(int u){

	visited[u] = true;
	for(unsigned int i = 0; i < neigh[u].size(); ++i){
		int v = neigh[u][i];
		if(visited[v] == false)
			DFS(v);
	}
	st.push(u);
}


void DFST(int u){

	visited[u] = true;
	components[count].push_back(u);
	for(unsigned int i = 0; i < neighT[u].size(); ++i){
		int v = neighT[u][i];
		if(visited[v] == false)
			DFST(v);
	}
}


void Kosaraju(){

	for(int i = 1; i <= N; ++i){
		if(visited[i] == false){
			DFS(i);
		}
	}

	visited.assign(N+1, false);

	while(!st.empty()){
		int u = st.top();
		st.pop();
		if(visited[u] == false){
			DFST(u);
			count++;
		}
	}
}


void write(){

	out << count << "\n";
	for(int i = 0; i < count; ++i){
		for(int j = 0; j < components[i].size(); ++j){
			out << components[i][j] << " ";
		}
		out << "\n";
	}
}



int main(){

	read();
	Kosaraju();
	write();
}