Cod sursa(job #426227)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 26 martie 2010 17:07:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 200002
#define f first
#define s second

int n, m, nr, comp, viz[nmax], min_level[nmax], level[nmax], last[nmax];
vector<int> v[nmax];
vector<int> sol[nmax];
pair<int, int> st[nmax];

void print(int x)
{
  if(last[x]!=comp)
  {
    sol[comp].push_back(x);
    last[x]=comp;
  }
}

void dfs(int nod)
{
  viz[nod] = 1;
  min_level[nod] = level[nod];

  for(vector<int>::iterator it = v[nod].begin(); it!=v[nod].end(); it++)
    if(!viz[*it])
    {
      level[*it] = level[nod] + 1;
      st[++nr] = make_pair(min(nod, *it), max(nod, *it));
      dfs(*it);
      min_level[nod] = min(min_level[nod], min_level[*it]);

      if(min_level[*it] >= level[nod])
      {
        comp++;
        while(st[nr] != make_pair(min(nod, *it), max(nod, *it)))
        {
          print(st[nr].f);
          print(st[nr].s);
          nr--;
        }
        print(st[nr].f);
        print(st[nr].s);
        nr--;
      }
    }
    else
    {
      if (level[*it] < level[nod] - 1)
        st[++nr] = make_pair(min(nod, *it), max(nod, *it));

      min_level[nod] = min(min_level[nod], level[*it]);
    }

}

int main()
{
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);
  scanf("%d %d\n", &n, &m);

  int i, x, y;
  for(i = 1; i <= m; i++)
  {
    scanf("%d %d\n", &x, &y);

    v[x].push_back(y);
    v[y].push_back(x);
  }

  dfs(1);

  printf("%d\n",comp);
  for(int i = 1; i <= comp; i++)
  {
    for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); it++)
       printf("%d ",*it);
    printf("\n");
  }
  return 0;
}