Cod sursa(job #265841)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 24 februarie 2009 16:27:14
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 4.63 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;      
                nrBC++;    
                while (stackx[top] != s || stacky[top] != it->x)    
                 {   
					 if (!viz[stackx[top]])
				            {
								biconex[++biconex[0]] = stackx[top];
								viz[stackx[top]] = 1;
				            }
				     if (!viz[stacky[top]])
				            {
								biconex[++biconex[0]] = stacky[top];
								viz[stacky[top]] = 1;
				            }
                      top--;    
                 }    
                    if (!viz[stackx[top]])
				            {
								biconex[++biconex[0]] = stackx[top];
								viz[stackx[top]] = 1;
				            }
				     if (!viz[stacky[top]])
				            {
								biconex[++biconex[0]] = stacky[top];
								viz[stacky[top]] = 1;
				            }  
                    top--; 
                    int aux = biconex[0];
					while (biconex[aux] != -1)
					{
						viz[biconex[aux]] = 0;
						aux--;
					}
            }    
   
            }    
         }    
        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);          
    printf("%d\n", nrBC);      
    for(int i = 1; i <= biconex[0]; i++)      
     {      
         if (biconex[i] != -1)      
         {      
                printf("%d ",biconex[i]);      
         }      
          else     
           {      
               printf("\n");          
           }      
     }      
     
    return 0;      
     
}