Cod sursa(job #265822)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 24 februarie 2009 15:56:49
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 4.14 kb
#include<stdio.h>   

struct Nod {   
    int x;   
    Nod *next;   
};   
Nod *a[100001];   
int p[100001];   
int viz[100001];   
int stackx[100001];   
int stacky[100001];
int nrBC;   
int top;   
int nrf;   
int n,m,x,y;   
int sn[100001];   
int biconex[400001];   
int art[100001];   
int smin[100001];   
  
int min(int a, int b)   
{   
    if (a > b) return b;   
    return a;   
}   
int insert(Nod *&u, int val)   
{   
    Nod *q = new Nod;   
    q -> x = val;   
    q -> next = u;   
    u = q;   
    return 0;   
}   
int dfs(int s, int niv)   
{   
    sn[s] = niv;   
    for(Nod *it = a[s]; it != NULL; it = it -> next)   
     if (!sn[it -> x])   
     {   
      p[it -> x] = s;   
      dfs(it -> x, niv + 1);   
     }   
    return 0;   
}   
int dfmin(int s)   
{   
    viz[s] = 1;   
    int mini = smin[s];   
    for(Nod *it = a[s]; it != NULL; it = it -> next)   
     if ((it -> x) != p[s])   
      if (mini > sn[it->x]) mini = sn[it->x];   
    smin[s] = mini;   
    for(Nod *it = a[s]; it != NULL; it = it -> next)   
     if (!viz[it -> x])   
      smin[s] = min(smin[s], dfmin(it -> x));   
  
    return smin[s];   
}   
/*******************  Determinarea punctelor de articulatie  
int dfArt(int s)  
{  
    viz[s] = 1;  
    for(Nod *it = a[s]; it != NULL; it = it -> next)  
     if (!viz[it->x])  
     {  
      if (smin[it->x] >= sn[s]) art[s] = 1;  
      dfArt(it->x);  
     }  
    return 0;  
}/**///**********************  
int df2conex(int s)  
{  
    viz[s] = 1;  
    for(Nod *it = a[s]; it != NULL; it = it -> next)  
     if (it -> x != p[s])  
     {  
        if (viz[it -> x] && sn[it -> x] <= sn[s])  
         {  
           stackx[++top] = s;  
           stacky[top] = it -> x;  
         }  
 
        if (!viz[it->x])  
         {  
           stackx[++top] = s;  
           stacky[top] = it -> x;  
           df2conex(it -> x);  
           if (smin[it -> x] >= sn[s])  
            {  
                biconex[++biconex[0]] = -1;  
                biconex[++biconex[0]] = -1;  
                nrBC++;  
                while (stackx[top] != s || stacky[top] != it->x)  
                 {  
                      biconex[++biconex[0]] = stackx[top];  
                      biconex[++biconex[0]] = stacky[top];  
                      top--;  
                 }  
 
                    biconex[++biconex[0]] = stackx[top];  
                    biconex[++biconex[0]] = stacky[top];  
                    top--;  
            }  
 
            }  
         }  
        return 0;  
     }  
void InitViz()  
{  
    for(int i = 1; i <= n; i++)  
     viz[i] = 0;  
}  
int main()  
{  
    freopen("biconex.in", "r", stdin);  
    freopen("biconex.out", "w", stdout);  
 
    scanf("%d %d", &n, &m);  
    for(int i = 1; i <= m; i++)  
    {  
     scanf("%d %d", &x, &y);  
     insert(a[x], y);  
     insert(a[y], x);  
    }  
    // nivelul fiecarui nod  
    dfs(1,1);  
    // nivelul minim la care se poate ajunge prin intermediul subarborelui  
    for(int i = 1; i <= n; i++)  
     smin[i] = sn[i];  
    InitViz();  
    dfmin(1);  
 
  /* determina punctele de articulatie  
     for(int i = 1; i <= n; i++)  
     viz[i] = 0;  
    dfArt(1);  
    for(int i = 1; i <= n; i++)  
     if (p[i] == 1) nrf++;  
     art[1] = 0;  
    if (nrf > 1) art[1] = 1;  */  
  
  
    // determina componente biconexe   
    InitViz();   
    df2conex(1);   
    InitViz();   
    printf("%d\n", nrBC);   
    for(int i = 3; i <= biconex[0]; i+=2)   
     {   
         if (biconex[i] != -1)   
         {   
          if (viz[biconex[i]] == 0)   
            {   
                printf("%d ",biconex[i]);   
                viz[biconex[i]] = 1;   
            }   
          if (viz[biconex[i+1]] == 0)   
            {   
                printf("%d ",biconex[i+1]);   
                viz[biconex[i+1]] = 1;   
            }   
         }   
          else  
           {   
               printf("\n");   
               InitViz();   
           }   
     }   
  
    return 0;   
  
}