Cod sursa(job #926808)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 25 martie 2013 13:06:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<vector>
#include<set>

using namespace std;

#define max_n 100010
#define max_m 200010

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

struct stiva{
	int a , b;
}stack[max_m];

vector<int>L[max_n];
set<int>Sol[max_m];
int Viz[max_n];
int a , b , nod , nod2 , n , m , vf , k;
int Up[max_n];

void read(){
	f>>n>>m;
	for(int  i = 1 ; i <= m ; i++){
		f>>a>>b;
		L[a].push_back(b);
		L[b].push_back(a);
	}
}

void dfs(int nod , int niv , int T){
	Viz[nod] = 1; Up[nod] = niv;
	int nod2;
	for(int i = 0 ; i < L[nod].size() ; i++){
		nod2 = L[nod][i];
		if(nod2 == T)
			continue;
		if(!Viz[ nod2 ]){
			stack[++vf].a = nod; stack[vf].b = nod2;
			dfs(nod2 , niv+1 , nod);
			if(niv <= Up[nod2] && vf!=0){
				k++;
				while(stack[vf].a!=nod || stack[vf].b!=nod2){
					Sol[k].insert(stack[vf].a); Sol[k].insert(stack[vf].b);
					vf--;
				}
				Sol[k].insert(stack[vf].a); Sol[k].insert(stack[vf].b);
				vf--;
			}
		}
		if(Up[nod2] < Up[nod])
			Up[nod] = Up[nod2];
		
	}
	
}

void print(){
	set<int>::iterator it;
	g<<k<<"\n";
	for(int i=1;i<=k;i++){
		for(it = Sol[i].begin() ; it != Sol[i].end() ; it++)
			g<<(*it)<<" ";
		g<<"\n";
	}
}

int main(){
	
	read();
	
	for(int i = 1 ; i <= n ; i++)
		if(!Viz[i])
			dfs(i , 1 , 0);
	
	print();
	
	return 0;
}