Cod sursa(job #1464676)

Utilizator Tester01tester Tester01 Data 24 iulie 2015 11:06:26
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.42 kb
#include <fstream>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define Nmax 100013
#define pb push_back
class cell {
 public :
        int node;
        cell *prev;
        cell(int a, cell *l) {node=a; prev=l;};
    };
     
class UndirectedGraph {

     private :
               cell *adj[Nmax];
               stack < pair<int,int > > St;
               vector < vector <int> > V;
               vector <int> Bic;
               bool used[Nmax];
               int father[Nmax];
               int level[Nmax];
               int levelMin[Nmax];
               
               void __build_solution(int a,int b){
               	bool freq[Nmax];
               	 while(St.top().first!=a){
               	 	int x = St.top().first;
               	 	int y = St.top().second;
               	 	if (!freq[x]) Bic.pb(x); 
               	 	if (!freq[y]) Bic.pb(y);
					++freq[x];
               	 	++freq[y];
               	 	St.pop(); 
                   }  
    	        if (!freq[a]) Bic.pb(a); 
         	 	if (!freq[b]) Bic.pb(b); 
                 St.pop();
                 V.pb(Bic);
                 Bic.clear();
                }
                 
     public : 
              int cntBiconected = 0;
              UndirectedGraph(int nodes,int edges) {
			                for (int i=1;i<=nodes;++i) { 
							   adj[i]=NULL; 
							   father[i]=i; 
							   level[i]=levelMin[i]=Nmax;
						    }
						level[1]=1;
						levelMin[1]=1;
              };

              void add(int a,int b){
              	  cell *node = new cell(a,adj[b]); adj[b]=node;
              	        node = new cell(b,adj[a]); adj[a]=node;
  	          }
              
              void dfs(int node) { 
                 used[node]=1;
                 for (cell *to = adj[node];to;to=to->prev){
				     //return edge
                 	 if (father[node]!=to->node) { 
            	       if (used[to->node]) {                                          
                          if (level[to->node]<level[node]) St.push({node,to->node});
                          levelMin[node]=min(levelMin[node],level[to->node]);
                         }
                       //direct edge
                       if (!used[to->node]) { 
					      father[to->node]=node;
				          levelMin[to->node]=level[to->node]=level[node]+1;
				          St.push({node,to->node});
					      dfs(to->node);
					      levelMin[node]=min(levelMin[node],levelMin[to->node]);
					      /*if the vertex-son is linked directly with his father, or 
			                it belongs to one of his sons subtrees, result we have a new component*/
					      if (levelMin[to->node]>=level[node]){ 
					          ++cntBiconected;
					          __build_solution(node,to->node);
					       }
                        } 
                 
                     }
                  }
               } 
			   
			   void showSol(){
			    for (int i=0;i<V.size();++i){
			    	for (int j=0;j<V[i].size();++j)
			    	  cout<<V[i][j]<<" ";
			    	  cout<<"\n";
			    }
		       }
    };

int a,b,n,m;
int main(void) {
 cin>>n>>m; 
 UndirectedGraph Graph(n,m);
 for (int i=1;i<=m;++i) {
   	cin>>a>>b;
   	Graph.add(a,b);
   }
  Graph.dfs(1);
  cout<<Graph.cntBiconected<<"\n"; 
  Graph.showSol();
 return 0;
}