Cod sursa(job #1392942)

Utilizator c0rn1Goran Cornel c0rn1 Data 18 martie 2015 23:39:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#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;
set<int> auxSol;

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)
         auxSol.insert(sol[i][j]);
      for (set<int>::iterator it = auxSol.begin(); it != auxSol.end(); ++it)
         printf("%d ", (*it));
      auxSol.clear();
      printf("\n");
   }
}

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

   return 0;
}