Cod sursa(job #1464883)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 25 iulie 2015 22:09:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.93 kb
#include <fstream>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
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];
                memset(freq,0,sizeof freq);
                 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();
                 sort(Bic.begin(),Bic.end());
                 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;
}