Cod sursa(job #853947)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 12 ianuarie 2013 16:32:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

vector <int> vecini[100009];
vector <int> solutie[100009];
vector <int> stack;
int totmaisus[100009];
int catdesus[100009];//nivelul
int viz[100009];
int n,m,nr;


void init(){
	for (int i=1;i<=n;i++){
		viz[i]=0;
	}
}

void citeste(){
	in>>n>>m;
	for (int i=1;i<=m;i++){
		int x,y;
		in>>x>>y;
		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}
}

void parc_ad(int nod,int nivel, int tata){
	totmaisus[nod]=nivel;
	catdesus[nod]=nivel;
	stack.push_back(nod);
	for (int i=0;i<vecini[nod].size();i++)
	{
		int x=vecini[nod][i];
		if (catdesus[x]==0)
		{
			stack.push_back(nod);
			parc_ad(x,nivel+1,nod);
			if (totmaisus[nod]>totmaisus[x]){
				totmaisus[nod]=totmaisus[x];
			}else
				if (totmaisus[x]>=nivel){
					int m=stack.size()-1;
					int j;
					nr++;
					while (nod!=stack[m]){
						if (viz[stack[m]]==0){
							solutie[nr].push_back(stack[m]);
							viz[stack[m]]=1;
						}
						--m;
						stack.pop_back();
					}
				if (viz[stack[m]]==0) {
					solutie[nr].push_back(stack[m]);
				}
				stack.pop_back();
				for(int j=0;j<solutie[nr].size();j++)
						viz[solutie[nr][j]]=0;
				
				}
		}else
			if ((catdesus[x]<totmaisus[nod]) && x!=tata)
				totmaisus[nod]=catdesus[x];
			
		
	}
	}
int main(){
		init();
		int i,j;
		citeste();
		for ( i=1;i<=n;i++)
			if (catdesus[i]==0) parc_ad(i,1,0);
			
		out<<nr<<'\n';
		for ( i=1;i<=nr;i++){
			for (j=0;j<solutie[i].size();j++)
				out<<solutie[i][j]<<' ';
		
			out<<'\n';
		}
	return 0;
		}