Cod sursa(job #1041435)

Utilizator RobertSSamoilescu Robert RobertS Data 25 noiembrie 2013 20:23:33
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;


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


#define MAX_N 10000
int n, m;
vector<int> list[MAX_N];
vector<int> cmp[MAX_N];
int contor=-1;
stack<pair<int,int> >st;
int lvl[MAX_N];

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

bool viz[MAX_N];


void df(int nod, int niv, int father){
	viz[nod] = true;
	
	lvl[nod] = niv;
	int next;
	
	for(size_t i=0; i<list[nod].size(); i++){
		next =  list[nod][i];
		
		if(next == father)
			continue;
		
		if(!viz[next]) {
			
			pair<int,int> myPair = make_pair(nod,next);
			st.push(myPair);
			df(next,niv+1, nod);
			
			if(lvl[next] >= lvl[nod] && st.size() ){
				
				pair<int,int> p = make_pair(nod,next);
				contor ++;
				cmp[contor].push_back(st.top().second);
				while(st.top() != p ){
					cmp[contor].push_back(st.top().first);
					st.pop();
				}
				cmp[contor].push_back( st.top().first);
				st.pop();
			}
			
		}
		
		if(lvl[next] < lvl[nod]){
			lvl[nod] = lvl[next];
		}
			
	}
	
	

}

int main(){
	
	read();
	for(int i=1; i<=n; i++){
		if(!viz[i]) df(i,1,0);
	}
	
	
	fout << contor +1<< '\n';
	for(size_t i=0; i<=contor; i++){
		for(size_t j=0; j<cmp[i].size(); j++){
			fout << cmp[i][j] << " ";
		}
		fout << endl;
	}
	
return 0;
}