Cod sursa(job #2292148)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 29 noiembrie 2018 00:04:43
Problema Componente biconexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef pair<int,int> muchie;

const int NMAX = 100005;
const int MMAX = 200005;

vector<vector<int>> G;

vector<int> low;
vector<int> id;
stack<muchie> st;

int N,M;

int ix = 0;

vector<set<int>> sol;

void dfs(int at, int from) {
   low[at] = id[at] = ix++;

   for (auto node : G[at]) {
      if (node == from) {
         continue;
      }

      if (id[node] == -1) {
         st.push(make_pair(at, node));
         dfs(node, at);
         low[at] = min(low[at], low[node]);
         if (low[node] >= id[at]) {
            set<int> bc;
            while (!st.empty()) {
               muchie p = st.top();
               st.pop();
               int n1 = p.first;
               int n2 = p.second;
               bc.insert(n1);
               bc.insert(n2);

               if ((n1 == at && n2 == node)) {
                  break;
               }
            }
            sol.push_back(bc);
         }
      } else {
         low[at] = min(low[at], id[node]);
      }
   }
}

int main() {
   freopen("biconex.in",  "r", stdin);
   freopen("biconex.out", "w", stdout);

   scanf("%d %d", &N, &M);

   low = vector<int>(N+1, 0);
   id  = vector<int>(N+1, -1);
   G = vector<vector<int>>(N+1);

   for (int i = 0; i < M; ++i) {
      int x,y;
      scanf("%d %d", &x, &y);
      G[x].push_back(y);
      G[y].push_back(x);
   }

   dfs(1, -1);

   printf("%d\n", int(sol.size()));
   for (auto bc : sol) {
      for (auto elm : bc) {
         printf("%d ", elm);
      }
      printf("\n");
   }

   fclose(stdin);
   fclose(stdout);
   return 0;
}