Cod sursa(job #265549)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 24 februarie 2009 00:45:41
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 3.77 kb
#include<stdio.h>
struct NodStiva {
    int x;
    int y;
};
struct Nod {
    int x;
    Nod *next;
};
Nod *a[100001];
int p[100001];
int viz[100001];
NodStiva stack[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])
         {
           stack[++top].x = s;
           stack[top].y = it -> x;
         }

        if (!viz[it->x])
         {
           stack[++top].x = s;
           stack[top].y = it -> x;
           df2conex(it -> x);
           if (smin[it -> x] >= sn[s])
            {
                biconex[++biconex[0]] = -1;
                biconex[++biconex[0]] = -1;
                nrBC++;
                while (stack[top].x != s || stack[top].y != it->x)
                 {
                      biconex[++biconex[0]] = stack[top].x;
                      biconex[++biconex[0]] = stack[top].y;
                      top--;
                 }

                    biconex[++biconex[0]] = stack[top].x;
                    biconex[++biconex[0]] = stack[top].y;
                    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;

}