Cod sursa(job #2253957)

Utilizator b10nd3Oana Mancu b10nd3 Data 4 octombrie 2018 16:47:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

#define MAX 100005

vector<int> adj[MAX], lvl, low;
vector < vector<int> > sol;
stack < pair<int,int> > st;

void createComponent(int a, int b){
   vector<int> comp;
   int x,y;
   
   do{
      x=st.top().first; y=st.top().second;
	  st.pop();
	  comp.push_back(x); comp.push_back(y);	  
   }while(x!=a || y!=b);
   sol.push_back(comp);
}


void dfs(int n,int from, int level){
	low[n]=lvl[n]=level;
	
	vector<int> :: iterator it;
	for(it=adj[n].begin(); it!=adj[n].end();it++){
		if(*it==from) continue;
		if(lvl[*it]==-1){
			st.push(make_pair(n,*it));
			dfs(*it,n,level+1);
			low[n]=min(low[n],low[*it]);
			if(low[*it]>=lvl[n]) //nu ajung mai sus prin fii printr-o muchie de intoarcere
			    createComponent(n,*it);
		}
		else // => muchie intoarcere
		  low[n]=min(low[n],lvl[*it]);
	}
}


int main(){
	ifstream in("biconex.in"); ofstream out("biconex.out");
	int i,n,m,x,y;
	
	//cirire
	in>>n>>m;
	lvl.resize(n+1); low.resize(n+1);
	lvl.assign(n+1,-1); 
	
	for(i=0;i<m;i++){
		in>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	//parc adancime + rezolvare
	dfs(1,0,0);
	
    //afisare sol
    out<<sol.size()<<'\n';
	for(i=0;i<sol.size();i++){
    	sort(sol[i].begin(),sol[i].end());
    	sol[i].resize( distance( sol[i].begin(),unique( sol[i].begin(),sol[i].end() ) ) );
    	for(int j=0;j<sol[i].size();j++) 
    	   out<<sol[i][j]<<" ";
    	out<<'\n';   
	}

	in.close(); out.close();
	return 0;
}