Cod sursa(job #1392904)

Utilizator c0rn1Goran Cornel c0rn1 Data 18 martie 2015 23:06:20
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 100008

using namespace std;

int n, m;
vector<int> v[NMAX];
int depth[NMAX], lowp[NMAX], nrDfs;
stack<pair<int, int> > st;
vector<int> sol[NMAX];
int nrComp;

void read()
{
   scanf("%d %d\n", &n, &m);
   int x, y;
   for (int i = 1; i <= m; ++i){
      scanf("%d %d\n", &x, &y);
      v[x].push_back(y);
      v[y].push_back(x);
   }
   for (int i = 1; i <= n; ++i){
      depth[i] = lowp[i] = -1;
   }
}

void dfs(int x, int p) /// p -> x
{
   int y;
   depth[x] = lowp[x] = nrDfs++;
   for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it){
      y = (*it);
      if (y != p && depth[y] < depth[x])
         st.push(make_pair(x, y));
      if (depth[y] == -1){
         dfs(y, x);
         lowp[x] = min(lowp[x], lowp[y]);
         if (depth[x] <= lowp[y]){
               /// salvare solutie
            if (st.top().first == x && st.top().second == y)
               sol[nrComp].push_back(st.top().second);
            sol[nrComp].push_back(st.top().first);
            while (st.top().first != x || st.top().second != y){
               st.pop();
               sol[nrComp].push_back(st.top().first);
            }
            st.pop();
            ++nrComp;
         }
      }
      else if (y != p){
         lowp[x] = min(lowp[x], depth[y]);
      }
   }
}

void write()
{
   printf("%d\n", nrComp);
   for (int i = 0; i < nrComp; ++i){
      for (int j = 0; j < sol[i].size(); ++j)
         printf("%d ", sol[i][j]);
      printf("\n");
   }
}

int main()
{
   freopen("biconex.in", "r", stdin);
   freopen("biconex.out", "w", stdout);
   read();
   dfs(1, -1);
   write();

   return 0;
}