Cod sursa(job #1125310)

Utilizator fhandreiAndrei Hareza fhandrei Data 26 februarie 2014 16:52:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb
// Include
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

// Definitii
#define pb push_back

// Constante
const int sz = (int)1e5+1;

// Functii
void dfs(int node);
void reverseDfs(int node);

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

int nodes, edges;

int visited[sz];

vector<int> graph[sz], reverseGraph[sz]; // Graful si graful transpus
stack<int> nodesStack; // Stiva in care voi retine nodurile in ordinea 

vector<int> answer;
vector< vector<int> > answers;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo;
	while(edges--)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		reverseGraph[rTo].pb(rFrom);
	}
	
	// Parcurge in adancime toate nodurile
	for(int i=1 ; i<=nodes ; ++i)
		dfs(i);
	
	// Voi considera ca nodurile vizitate sunt in stiva, iar cele nevizitate nu.
	// In acest mod, cand voi scoate un nod din stiva, il voi marca nevizitat (1)
	
	// Cat timp mai am elemente in stiva
	while(!nodesStack.empty())
	{
		// Iau valoarea nodului din varful stivei, ulterior stergandu-l
		int node = nodesStack.top();
		nodesStack.pop();
		
		// Fac o parcurgere in adancime din nodul curent pe graful transpus
		reverseDfs(node);
		
		if(answer.size())
		{
			answers.pb(answer);
			answer.clear();
		}
	}
	
	out << answers.size() << '\n';
	
	vector< vector<int> >::iterator it, end=answers.end();
	for(it=answers.begin() ; it!=end ; ++it)
	{
		vector<int>::iterator vit, vend=it->end();
		for(vit=it->begin() ; vit!=vend ; ++vit)
			out << *vit << ' ';
		out << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node)
{
	// Nu voi intra intr-un nod deja vizitat
	if(visited[node])
		return;
	
	// Marchez nodul ca vizitat
	visited[node] = true;
	
	// Iau toti vecinii nodului curent
	vector<int>::iterator it, end=graph[node].end();
	
	// Continui parcurgerea in adancime din fiecare vecin al nodului curent
	for(it=graph[node].begin() ; it!=end ; ++it)
		dfs(*it);
	
	// La intoarcerea din recursivitate (cand toti vecinii nodului curent sunt deja vizitati),
	// introduc nodul curent in stiva
	nodesStack.push(node);
}

void reverseDfs(int node)
{
	// Nu voi intra intr-un nod deja vizitat
	if(!visited[node])
		return;
	
	// Marchez nodul ca nevizitat - vezi (1)
	visited[node] = false;
	
	// Iau toti vecinii nodului curent
	vector<int>::iterator it, end=reverseGraph[node].end();
	
	// Continui parcurgerea in adancime din fiecare vecin al nodului curent
	for(it=reverseGraph[node].begin() ; it!=end ; ++it)
		reverseDfs(*it);
	
	// Fiecare parcurgere va determina cate o componenta tare conexa
	answer.pb(node);
}