Cod sursa(job #1107731)

Utilizator radu2004GOLD radu radu2004 Data 14 februarie 2014 11:02:10
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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,sol[100005];
FILE *f,*g;
void afis ()
{
     while (!st.empty())
       {
           sol[nr].push_back(st.back());
           st.pop_back();
       }
       nr++;

}
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;
            df (y);
            st.push_back(y);
            if (low[y]<low[x]) low[x]=low[y];
            if (use[x]<=low[y])
            {
                st.push_back(x);
                afis ();
            }
        }
         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");
 }
 x=st[0];

    return 0;
}