Cod sursa(job #303949)

Utilizator floringh06Florin Ghesu floringh06 Data 10 aprilie 2009 15:55:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FIN "biconex.in"
#define FOUT "biconex.out"
#define MAX_N 100005

int N, M, L, Res;
vector <int> A[MAX_N], B[MAX_N];
int deg[MAX_N];
int U[MAX_N], Vmin[MAX_N], Niv[MAX_N], T[MAX_N], Mark[MAX_N];
int Sx[MAX_N], Sy[MAX_N];

    void DFS(int nod)  
    {  
       int i;  
   
       U[nod] = 1;  
       Vmin[nod] = Niv[nod];  
   
       for (i = 0; i < deg[nod]; i++)  
           if (!U[A[nod][i]])  
           {   
             Niv[A[nod][i]] = Niv[nod] + 1;  
             T[A[nod][i]] = nod;  
  
             Sx[++L] = nod;  
             Sy[L] = A[nod][i];  
   
             DFS(A[nod][i]);  
   
             Vmin[nod] = min(Vmin[nod], Vmin[A[nod][i]]);  
   
             if (Vmin[A[nod][i]] >= Niv[nod])  
             {  
                 ++Res;  
  
                 for (; L >= 0 && (Sx[L + 1] != nod || Sy[L + 1] != A[nod][i]); L--)  
                 {  
                     if (Mark[Sx[L]] != Res)   
                     {  
                         Mark[Sx[L]] = Res;  
                         B[Res].push_back(Sx[L]);  
                     }  
   
                     if (Mark[Sy[L]] != Res)  
                     {  
                         Mark[Sy[L]] = Res;  
                         B[Res].push_back(Sy[L]);  
                     }  
                 }  
             }  
           }  
           else 
                if (A[nod][i] != T[nod]) 
                   Vmin[nod] = min(Vmin[nod], Niv[A[nod][i]]);  
    }  

    int main ()
    {
        int i, x, y;
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &N, &M);
        for (i = 1; i <= M; ++i)
        {
            scanf ("%d %d", &x, &y);
            A[x].push_back(y);
            A[y].push_back(x);
        }
        for (i = 1; i <= N; ++i) deg[i] = A[i].size ();
        DFS (1);
        printf ("%d\n", Res);
        for (i = 1; i <= Res; ++i)
        {
            x = B[i].size ();
            for (int j = 0; j < x; ++j)
                printf ("%d ", B[i][j]);
            printf ("\n");
        }
        
        return 0;
    }