Cod sursa(job #639022)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 22 noiembrie 2011 09:50:33
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
using namespace std;
vector <int> v[100100],s,tmp;
vector <vector <int> > sol; 
int n,lvl[100100],low[100100];
void afis() {
	unsigned int i,j;
	ofstream out("biconex.out");
	out<<sol.size()<<'\n';
	for(i=0;i<sol.size();i++) {
		for(j=0;j<sol[i].size();j++)
			out<<sol[i][j]<<" ";
		out<<'\n';
		}
	out.close();
}
void avem_sol(int nod) {
	while(s.back()!=nod) {
		tmp.push_back(s.back());
		s.pop_back();
		}
	tmp.push_back(nod);
	sol.push_back(tmp);
	tmp.clear();
}
void DFS(int nod,int tata,int level) {
	unsigned int i,vecin;
	lvl[nod]=low[nod]=level;
	for(i=0;i<v[nod].size();i++) {
		vecin=v[nod][i];
		if(vecin==tata) continue;
		if(!lvl[vecin]) {
			s.push_back(nod);
			DFS(vecin,nod,level+1);
			low[nod]=min(low[nod],low[vecin]);
			if(low[vecin]>=lvl[nod])
				avem_sol(nod);
			}
		else
			low[nod]=min(low[nod],lvl[vecin]);
		}
}
void citire() {
	int i,m,x,y;
	ifstream in("biconex.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		}
	in.close();
}
int main() {
	citire();
	//s.push_back(1);
	DFS(1,0,1);
	afis();
	return 0;
}