Cod sursa(job #868907)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 31 ianuarie 2013 19:16:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#define nmax 100100
using namespace std;

stack < pair<int,int> > St;
vector <int> G[nmax],Answer[nmax];
int N,NrCb,Nivel[nmax],Low[nmax];

void Add(int A,int B) {
	
	int x,y;
	
	++NrCb;
	
	do {
		x=St.top().first;
		y=St.top().second;
		Answer[NrCb].push_back(y);
		St.pop();
	}while(A!=x && B!=y);
	
	Answer[NrCb].push_back(x);
	
}
void DFS(int Nod,int Tata) {
	
	int i,Vecin;
	
	Nivel[Nod]=Nivel[Tata]+1;
	Low[Nod]=Nivel[Nod];
	
	for(i=0;i<G[Nod].size();i++) {
		
		if((Vecin=G[Nod][i])==Tata)
			continue;
		
		if(!Nivel[Vecin]) {
			St.push(make_pair(Nod,Vecin));
			DFS(Vecin,Nod);
			if(Low[Vecin]>=Nivel[Nod])
				Add(Nod,Vecin);
			}
		
		Low[Nod]=min(Low[Nod],Low[Vecin]);
		
		}
	
}
void Read() {
	
	int x,y,M;
	ifstream in("biconex.in");
	in>>N>>M;
	
	while(M--) {
		in>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
		}
	
	in.close();
	
}
void Write() {
	
	int i,j;
	ofstream out("biconex.out");
	out<<NrCb<<'\n';
	
	for(i=1;i<=NrCb;i++) {
		for(j=0;j<Answer[i].size();j++)
			out<<Answer[i][j]<<' ';
		out<<'\n';
		}
	
	out.close();
	
}
int main() {
	
	Read();
	DFS(1,0);
	Write();
	
	return 0;
	
}