Cod sursa(job #479430)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 24 august 2010 01:01:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
#define  nmax 100005

using namespace std;

const char iname[] = "ctc.in";
const char oname[] = "ctc.out";

ifstream fin(iname);
ofstream fout(oname);

vector<int> Graph[nmax];
vector<int> InvGraph[nmax];
vector<int> Road[nmax];

int N, M, i, j, Father[nmax], sol, viz[nmax], viz2[nmax], k, x, y, nr;

void DFS1(int nod)
{	
	viz[nod] = 1;
	for(vector<int>::iterator it = Graph[nod].begin(); it != Graph[nod].end(); ++it)
		if(!viz[*it])
			DFS1(*it);
	Father[++k] = nod;
}

void DFS2(int nod)
{	
	viz[nod] = 0;
	for(vector<int>::iterator it = InvGraph[nod].begin(); it != InvGraph[nod].end(); ++it)
		if(viz[*it])
			DFS2(*it);
	Road[sol].push_back(nod);
}
	
int main()
{
	fin >> N >> M;
	for(i = 1; i <= M; i ++)
	{
		fin >> x >> y;
		Graph[x].push_back(y);
		InvGraph[y].push_back(x);
	}
	
	for(i = 1; i <= N; i ++)
		if(!viz[i])
			DFS1(i);
	for(i = N; i >= 1; i --)
		if(viz[Father[i]])
		{
			++ sol;
			DFS2(Father[i]);
		}
	fout << sol << "\n";
	for(i = 1; i <= sol; i ++)
	{
		for(j = 0; j < Road[i].size(); j ++)
			fout << Road[i][j] << " ";
		fout << "\n";
	}
		
	return 0;
}