Cod sursa(job #1394088)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 19 martie 2015 23:40:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;


class Graph {
 public:
   Graph(int _N) : N(_N) {
     edges.assign(N, vector<int>());
     dfn.assign(N, -1);
     low_link.assign(N, -1);
   }
   void addEdge(int x, int y) {
     edges[x].push_back(y);
     edges[y].push_back(x);
   }
   vector <vector <int> > solve() {
     for (int i = 0; i < N; ++i) {
       if (dfn[i] == -1) {
         tarjan(i, 1, -1);
       }
     }
     return components;
   }
 private:
   vector <vector <int> > edges, components;
   vector <int> dfn, low_link;
   stack <pair <int, int> > st;
   int N;

   void pop_stack(pair <int, int> cur_edge) {
     vector <int> partial;
     while(!st.empty()) {
       int y = st.top().second;
       st.pop();
       partial.push_back(y);
       if (y == cur_edge.second) {
         break;
       }
     }
     partial.push_back(cur_edge.first);
     components.push_back(partial);
   }
   void tarjan(int node, int father, int when) {
     dfn[node] = low_link[node] = when;

     for (auto neigh: edges[node]) {
       if (dfn[neigh] == -1) {
         st.push(make_pair(node, neigh));
         tarjan(neigh, node, when + 1);
         low_link[node] = min(low_link[node], low_link[neigh]);

         if (low_link[neigh] >= dfn[node]) {
           cerr << "articulatie " << node << "\n";
           pop_stack(make_pair(node, neigh));
         }
       } else if (neigh != father) {
         low_link[node] = min(low_link[node], dfn[neigh]);
       }
     }
   }
};
int main() {
  ifstream cin("biconex.in");
  ofstream cout("biconex.out");
  int N, M; cin >> N >> M;
  Graph G(N);
  while(M--) {
    int x, y; cin >> x >> y;
    x--; y--;
    G.addEdge(x, y);
  }
  vector <vector <int> > components = G.solve();
  cout << components.size() << "\n";
  for (auto it: components) {
    for (auto node: it) {
      cout << node + 1 << " ";
    }
    cout << "\n";
  }
  return 0;
}