Cod sursa(job #265804)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 24 februarie 2009 15:28:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<stdio.h>
#include<stack>
#include<vector>
using namespace std;
FILE*fin=fopen("biconex.in","r");
FILE*fout=fopen("biconex.out","w");
#define nm 100005
#define pb push_back
#define mkp make_pair
#define x first
#define y second
vector<int>g[nm],ans[nm];
stack<pair<int,int> > stk;
int nrcb=0,level[nm],mlr[nm],used[nm],n,m;
void pmc(int a,int b)
{
      int m1,m2;
      nrcb++;
      do
      {
         m1=stk.top().x;m2=stk.top().y;
         stk.pop();
         ans[nrcb].pb(m2);
         
      }while(m1!=a||m2!=b);
      ans[nrcb].pb(m1);
}
void df(int nod,int father)
{
     int i,nnod;
     level[nod]=level[father]+1;
     mlr[nod]=level[nod];
     for(i=0;i<g[nod].size();i++)
     {
       nnod=g[nod][i];
       if(!used[nnod])
       {
         used[nnod]=1;
         stk.push(mkp(nod,nnod));
         df(nnod,nod);
         if(mlr[nnod]<mlr[nod]) mlr[nod]=mlr[nnod];
         if(mlr[nnod]>=level[nod]) pmc(nod,nnod);
       }
       else if(nnod!=father&&mlr[nnod]<mlr[nod]) mlr[nod]=mlr[nnod];
     }
}
int main()
{
    int a,b,i,j;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
      fscanf(fin,"%d%d",&a,&b);
      g[a].pb(b);
      g[b].pb(a);
    }
    memset(used,0,sizeof(used));
    level[0]=0;used[1]=1;
    df(1,0);
    fprintf(fout,"%d\n",nrcb);
    for(i=1;i<=nrcb;i++)
    {
      for(j=0;j<ans[i].size();j++)
        fprintf(fout,"%d ",ans[i][j]);
      fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}