Cod sursa(job #863236)

Utilizator fhandreiAndrei Hareza fhandrei Data 23 ianuarie 2013 17:06:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 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, int start);
void printdfs(int node);

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

int nodes, edges;

bool inStack[sz];
bool visited[sz];

vector<int> graph[sz];
vector<int> reversedGraph[sz];
stack<int> nodesStack;
vector< vector<int> > answer;
vector<int> answerTemp;

// Main
int main()
{
	in >> nodes >> edges;
	int rFrom, rTo; // Teo: <3
	for(int i=1 ; i<=edges ; ++i)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		reversedGraph[rTo].pb(rFrom);
	}
	
	while((int)nodesStack.size() != nodes)
	{
		for(int i=1 ; i<=nodes ; ++i)
		{
			if(inStack[i])
				continue;
			
			dfs(i, i);
		}
	}
	
	while(!nodesStack.empty())
	{
		int current = nodesStack.top();
		nodesStack.pop();
		if(inStack[current])
		{
			printdfs(current);
			answer.pb(answerTemp);
			answerTemp.clear();
		}
	}
	
	out << answer.size() << '\n';
	vector<vector<int > >::iterator it, end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
	{
		vector<int>::iterator it2, end2 = it->end();
		for(it2=it->begin() ; it2!=end2 ; ++it2)
			out << *it2 << ' ';
		out << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node, int start)
{
	visited[node] = true;
	vector<int>::iterator it, end = graph[node].end();
	for(it=graph[node].begin() ; it!=end ; ++it)
		if(!visited[*it])
			dfs(*it, start);
	if(!inStack[node])
	{
		nodesStack.push(node);
		inStack[node] = true;
	}
}


void printdfs(int node)
{
	inStack[node] = false;
	answerTemp.pb(node);
	vector<int>::iterator it, end = reversedGraph[node].end();
	
	for(it=reversedGraph[node].begin() ; it!=end ; ++it)
	{
		if(inStack[*it])
			printdfs(*it);
	}
}