Cod sursa(job #732260)

Utilizator danieladDianu Daniela danielad Data 9 aprilie 2012 23:10:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<iostream>
#include<fstream>
#include<vector>
#define nmax 100001
#define min(a,b) (a<b)? a: b
using namespace std;
int n,m,vf=-1,k,viz[nmax],c[nmax],niv[nmax];
vector <int> s[nmax],v[nmax];
struct muchie{
	int a;
	int b;
}stiva[nmax];
void DFS(int i){
	viz[i]=1;
	c[i]=niv[i];
	for(int j=0;j<v[i].size();j++)
		if(viz[v[i][j]]==0){
			niv[v[i][j]]=niv[i]+1;
			vf++;
			stiva[vf].a=i;
			stiva[vf].b=v[i][j];
			DFS(v[i][j]);
			if(c[v[i][j]]>=niv[i]){
				while(stiva[vf].a!=i&&stiva[vf].b!=v[i][j]){
					s[k].push_back(stiva[vf].b);
					vf--;
				}
				s[k].push_back(i);
				s[k].push_back(v[i][j]);
				vf--;
				k++;
			}
			c[i]=min(c[i],c[v[i][j]]);
		}
		else
			c[i]=min(c[i],niv[v[i][j]]);
}
int main(){
	ifstream f("biconex.in");
	ofstream g("biconex.out");
	int x,y;
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	DFS(1);
	g<<k<<endl;
	for(int i=0;i<k;i++){
		for(int j=0;j<s[i].size();j++)
			g<<s[i][j]<<" ";
		g<<"\n";
	}
	return 0;
}