Cod sursa(job #1089996)

Utilizator radu2004GOLD radu radu2004 Data 22 ianuarie 2014 10:31:37
Problema Componente biconexe Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <vector>

using namespace std;
int i,n,use[100005],t[100005],m,x,y,nr;
vector <int> v[100005],st,sol[100005];
FILE *f,*g;
void afis (int x,int y)
{
     while (st.back ()!=y)
       {
           sol[nr].push_back(st.back());
           st.pop_back();
       }
       sol[nr++].push_back(st.back());
}
void df (int x)
{   int j;
    use[x]=use[t[x]]+1;
    st.push_back (x);
    for ( j=0;j<v[x].size();j++)
    {
        int y=v[x].at(j);
        if (((use[y]<use[x] && use[y]>0) || y==1 ) && t[x]!=y) afis (x,y);
           else if (use[y]==0) {t[y]=x;df (y);}
    }
    if (v[x].empty())
    {
        afis (x,t[x]);
    }
}
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);

 }
for (i=1;i<=n;i++)
 if (!use[i]) df (i);
 fprintf (g,"%d\n",nr+st.size()-1);
 for (i=0;i<nr;i++)
 {
    for (int k=0;k<sol[i].size();k++)
    {
        fprintf (g,"%d ",sol[i].at(k));
    }
    fprintf (g,"\n");
 }
 x=st.at(0);
 for (i=1;i<st.size();i++)
 {
     fprintf (g,"%d %d\n",x,st.at(i));
     x=st.at(i);
 }
    return 0;
}