Cod sursa(job #570433)

Utilizator andreioneaAndrei Onea andreionea Data 3 aprilie 2011 02:53:32
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
#include<stack>
#include<vector>
#include<iostream>
#define infile "ctc.in"
#define outfile "ctc.out"
void ctc (std::stack<int> &s, 
		 std::vector<std::vector<int> >& vec, 
		 std::vector<std::pair<int,int> >& atribut,
	     int nod, 
	     std::vector<std::vector<int> >& sol)
{
	static int timp = 0;
	atribut[nod].first = atribut[nod].second = timp;
	++ timp;	
	s.push(nod);
	std::vector<int>::iterator it;
	for(it = vec[nod].begin(); it != vec[nod].end(); ++it){
		if(atribut[*it].first == -1){
			ctc(s,vec,atribut,*it,sol);
			if(atribut[nod].second > atribut[*it].second)
				atribut[nod].second = atribut[*it].second;
		}
		else if(atribut[*it].first >= 0){
			if(atribut[*it].second < atribut[nod].second)
				atribut[nod].second = atribut[*it].second;
		}
	}
	if(atribut[nod].first == atribut[nod].second){
		std::vector<int> comp;
		int w;
		do{
			w = s.top();
			s.pop();
			comp.push_back(w);
			atribut[w].first = -2;
		}while(w!=nod);
		sol.push_back(comp);
	}
} 
int main()
{
	int n, m, i;
	std::stack<int> s;
	std::ifstream fin(infile);
	std::ofstream fout(outfile);
	fin >> n >> m;
	std::vector<std::vector<int> >vec;
	std::vector<std::pair<int,int> >atribut;
	std::vector<std::vector<int> > sol;
	for(i = 0; i<n; ++i){
		atribut.push_back(std::pair<int,int>(-1,-1));
		std::vector<int> v;
		vec.push_back(v);
	}
	for(i = 0; i<m; ++i){
		int x,y;
		fin >> x >> y;
		vec[x-1].push_back(y-1);
	}		
	for(i = 0; i<n; ++i)
		if(atribut[i].first == -1)
			ctc(s,vec,atribut,i,sol);
	
	fout<<sol.size()<<std::endl;
	for(i = 0; i<sol.size(); ++i){
		int j;
		for(j = 0; j<sol[i].size(); ++j)
			fout<<sol[i][j] + 1<<" ";
		fout<<std::endl;
	}
	fin.close();
	fout.close();
	return 0;
}