Cod sursa(job #1107760)

Utilizator radu2004GOLD radu radu2004 Data 14 februarie 2014 11:30:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <vector>

using namespace std;
int i,n,use[100005],t[100005],m,x,y,nr,low[100005];
vector <int> v[100005],st[3],sol[100005];
FILE *f,*g;
void afis (int x,int y)
{
     while (st[1].back()!=x || st[2].back() !=y)
       {
           sol[nr].push_back(st[2].back());
           st[1].pop_back();
           st[2].pop_back();
       }
       sol[nr].push_back(st[1].back());
       sol[nr++].push_back(st[2].back());
       st[1].pop_back();
       st[2].pop_back();

}
void df (int x)
{   int j;
    low[x]=use[x]=use[t[x]]+1;

    for ( j=0;j<v[x].size();j++)
    {
        int y=v[x][j];
        if (use[y]==0)
        {   t[y]=x;
            st[1].push_back(x);
            st[2].push_back (y);
            df (y);

            if (low[y]<low[x]) low[x]=low[y];
            if (use[x]<=low[y])
            {

                afis (x,y);
            }
        }
         else
            if (y!=t[x] && low[y]<low[x]) low[x]=low[y];


    }

}
int main()
{f=fopen ("biconex.in","r");
 g=fopen ("biconex.out","w");
 fscanf (f,"%d%d",&n,&m);
 for (i=1;i<=m;i++)
 {
     fscanf (f,"%d%d",&x,&y);
     v[x].push_back (y);
     v[y].push_back (x);

 }

df(1);
 fprintf (g,"%d\n",nr);
 for (i=0;i<nr;i++)
 {
    for (int k=0;k<sol[i].size();k++)
    {
        fprintf (g,"%d ",sol[i][k]);
    }
    fprintf (g,"\n");
 }


    return 0;
}