Cod sursa(job #902558)

Utilizator fhandreiAndrei Hareza fhandrei Data 1 martie 2013 15:01:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 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 reversedDFS(int node);

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

bool found;
int nodes, edges;

bool visited[sz];

vector<int> graph[sz], reversedGraph[sz];
stack<int> st;

vector< vector<int> > answer;
vector<int> answerTemp;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo;
	while(edges--)
	{
		in >> rFrom >> rTo;
		
		graph[rFrom].pb(rTo);
		reversedGraph[rTo].pb(rFrom);
	}
	
	for(int i=1 ; i<=nodes ; ++i)
		dfs(i);
	
	while(!st.empty())
	{
		found = false;
		reversedDFS(st.top());
		if(found)
		{
			answer.pb(answerTemp);
			answerTemp.clear();
		}
		st.pop();
	}
	
	out << answer.size() << '\n';
	
	vector< vector<int> >::iterator answerIT, answerEND=answer.end();
	for(answerIT=answer.begin() ; answerIT!=answerEND ; ++answerIT)
	{
		vector<int>::iterator it, end=answerIT->end();
		for(it=answerIT->begin() ; it!=end ; ++it)
			out << *it << ' ';
		out << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

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

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