Cod sursa(job #280254)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 13 martie 2009 12:03:53
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 7.65 kb
#include<stdio.h>   
  
struct Nod {   
    int x;   
    Nod *next;   
};   
Nod *a[100001];   
int p[100001];   
int viz[100001];   
int viz2[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];   
}   
  
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 (!viz2[stackx[top]])   
                            {   
                                biconex[++biconex[0]] = stackx[top];   
                                viz2[stackx[top]] = 1;   
                            }   
                     if (!viz2[stacky[top]])   
                            {   
                                biconex[++biconex[0]] = stacky[top];   
                                viz2[stacky[top]] = 1;   
                            }   
                      top--;   
                 }   
                    if (!viz2[stackx[top]])   
                            {   
                                biconex[++biconex[0]] = stackx[top];   
                                viz2[stackx[top]] = 1;   
                            }   
                     if (!viz2[stacky[top]])   
                            {   
                                biconex[++biconex[0]] = stacky[top];   
                                viz2[stacky[top]] = 1;   
                            }   
                    top--;   
                    int aux = biconex[0];   
                    while (biconex[aux] != -1)   
                    {   
                        viz2[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 componente biconexe   
    InitViz();   
    df2conex(1);   
    printf("%d", nrBC);   
    for(int i = 1; i <= biconex[0]; i++)   
     {   
         if (biconex[i] != -1)   
         {   
                printf("%d ",biconex[i]);   
         }   
          else  
           {   
               printf("\n");   
           }   
     }   
  
    return 0;   
  
}  
#include<stdio.h>

struct Nod {
    int x;
    Nod *next;
};
Nod *a[100001];
int p[100001];
int viz[100001];
int viz2[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];
}

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 (!viz2[stackx[top]])
				            {
								biconex[++biconex[0]] = stackx[top];
								viz2[stackx[top]] = 1;
				            }
				     if (!viz2[stacky[top]])
				            {
								biconex[++biconex[0]] = stacky[top];
								viz2[stacky[top]] = 1;
				            }
                      top--;
                 }
                    if (!viz2[stackx[top]])
				            {
								biconex[++biconex[0]] = stackx[top];
								viz2[stackx[top]] = 1;
				            }
				     if (!viz2[stacky[top]])
				            {
								biconex[++biconex[0]] = stacky[top];
								viz2[stacky[top]] = 1;
				            }
                    top--;
                    int aux = biconex[0];
					while (biconex[aux] != -1)
					{
						viz2[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 componente biconexe
    InitViz();
    df2conex(1);
    printf("%d", nrBC);
    for(int i = 1; i <= biconex[0]; i++)
     {
         if (biconex[i] != -1)
         {
                printf("%d ",biconex[i]);
         }
          else
           {
               printf("\n");
           }
     }

    return 0;

}