Cod sursa(job #280084)

Utilizator raula_sanChis Raoul raula_san Data 13 martie 2009 10:46:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include <stdio.h>
#include <stack>
#include <bitset>

using namespace std;

#define MAX_N 100001

stack < pair <int, int> > S;

struct nod
{
       int v;
       nod *next;

} *L[MAX_N], *Comp[MAX_N];

int Dfn[MAX_N], Lv[MAX_N], T[MAX_N], U[MAX_N];
int N, M, R, K;

bitset <MAX_N> B;

void Add(nod *&l, int nd)
{
     nod *p = new nod;
     p->v = nd;
     p->next = l;
     l = p;
}

void Dfs(int nd)
{
     Dfn[nd] = Dfn[T[nd]] + 1;
     Lv[nd] = Dfn[nd];
     U[nd] = 1;
     
     nod *p;
     
     for ( p = L[nd]; p; p = p->next )
     {
         if(p->v != T[nd] && Dfn[p->v] < Dfn[nd])
                 S.push(make_pair(nd, p->v));

         if(!U[p->v])
         {
                     T[p->v] = nd;
                     Dfs(p->v);
                     
                     if(Lv[p->v] < Lv[nd])
                                 Lv[nd] = Lv[p->v];
                     if(Lv[p->v] >= Dfn[nd])
                     {
                                 pair <int, int> nv;
                                 ++ K;
                                 while(!S.empty())
                                 {
                                      nv = S.top();
                                      S.pop();
                                                  
                                      Add(Comp[K], nv.second);
                                      
                                      if(nv.first == nd && nv.second == p->v) break;
                                 }
                                 Add(Comp[K], nv.first);
                     }
         }
         else if(Dfn[p->v] < Lv[nd] && T[nd] != p->v)
              Lv[nd] = Dfn[p->v];
    }
}

int main()
{
    freopen("biconex.in", "rt", stdin);
    freopen("biconex.out", "wt", stdout);
    
    int i, x, y;
    for ( scanf("%d %d", &N, &M), i = 1; i <= M; ++i )
    {
        scanf("%d %d", &x, &y);
        Add(L[x], y);
        Add(L[y], x);
    }

    for ( i = 1; i <= N; ++i )
        if(!U[i])
        {
                 T[i] = 0;
                 Dfs(i);
        }        

    printf("%d\n", K);
    
    for ( i = 1; i <= K; ++i )
    {
        B = 0;
        for ( nod *p = Comp[i]; p; p = p->next )
            if(!B[p->v])
            {
                         printf("%d ", p->v);
                         B[p->v] = 1;
            }
        printf("\n");
    }
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}