Cod sursa(job #1491589)

Utilizator azkabancont-vechi azkaban Data 25 septembrie 2015 18:37:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.8 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 UndirectedGraph {
   private :

      class cell {
         public :
              int node;
              cell *prev;
              cell(int a, cell *l) {node=a; prev=l;};
                };

            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;
}