Cod sursa(job #661326)

Utilizator johnny2008Diaconu Ion johnny2008 Data 14 ianuarie 2012 12:23:51
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
#define pb push_back
stack<int> q;
vector<int> vec[100001];
vector<int> grupa[100001];
int ct=0;
bool viz[100001];
int gr[100001];
int n,m;
void parcurg(int nod,int tata){
	
	viz[nod]=true;
	q.push(nod);
	int i;
	for(i=0;i<vec[nod].size();i++){
	
		if(viz[vec[nod][i]]==false)
			parcurg(vec[nod][i],nod);
		else{
			if(vec[nod][i]!=tata && gr[vec[nod][i]]==0){
				if(gr[vec[nod][i]]!=gr[nod] || gr[vec[nod][i]]==0){
				int w;
				ct++;
				while(w!=vec[nod][i]){
					w=q.top();
					if(gr[w]!=0){}
					else{
						grupa[ct].pb(w);
						gr[w]=ct;
					}
					if(w!=vec[nod][i])
						q.pop();
				}
				}
			
			}
		}
	}
}
void parcurg1(int nod){
	
	viz[nod]=false;
	int i;
	for(i=0;i<vec[nod].size();i++){
		
		if(viz[vec[nod][i]]==true){
			if(gr[nod]!=gr[vec[nod][i]]){
				ct++;
				grupa[ct].pb(nod);
				grupa[ct].pb(vec[nod][i]);
				
			}
			parcurg1(vec[nod][i]);
		}
		
	}
}
				

int main(){
	ifstream f("biconex.in");
	ofstream g("biconex.out");
	f>>n>>m;
	int i,j;
	for(i=1;i<=m;i++){
		int a,b;
		f>>a>>b;
		vec[a].pb(b);
		vec[b].pb(a);
	}
	parcurg(1,0);
	parcurg1(1);
	g<<ct<<"\n";
	for(i=1;i<=ct;i++){
		for(j=0;j<grupa[i].size();j++){
			g<<grupa[i][j]<<" ";
		}
		g<<"\n";
	}
	
	
	return 0;
}