Cod sursa(job #250953)

Utilizator FlorianFlorian Marcu Florian Data 1 februarie 2009 14:08:59
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<stdio.h>
#include<string.h>
#define Nmax 100003
#define min(a,b) ((a)<(b)?(a):(b))
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
struct Nod
 {
 int info;
 Nod *urm;
 };
Nod *prim[Nmax];
int n,df[Nmax],low[Nmax];
inline void insert(int x, int y)
 {
 Nod *p=new Nod;
 p->info=x;
 p->urm=prim[y];
 prim[y]=p;
 }
void read()
 {
 int m,x,y;
 fscanf(f,"%d %d",&n,&m);
 while(m--)
  {
  fscanf(f,"%d %d",&x,&y);
  insert(x,y);
  insert(y,x);
  }
 }
int vf,st[2][Nmax];
int nr;
int sol[Nmax];
Nod *S[Nmax];
void ins(int x, int y)
 {
 Nod *q=new Nod;
 q->info=y;
 q->urm=S[x];
 S[x]=q;
 }
void print()
 {
 int i;
 Nod *q;
 fprintf(g,"%d\n",nr);
 for(i=1;i<=nr;++i)
  {
  for(q=S[i];q;q=q->urm)
   fprintf(g,"%d ",q->info);
  fprintf(g,"\n");
  }
 }
void elim(int x, int y)
 {
  nr++;
  do
  {
    if(sol[st[0][vf]]!=nr)
     {
     sol[st[0][vf]]=nr;
     ins(nr, st[0][vf]);
     }
    if(sol[st[1][vf]]!=nr)
     {
     sol[st[1][vf]]=nr;
     ins(nr,st[1][vf]);
     }
    --vf;

   }
  while(st[0][vf+1] != x || st[1][vf+1] != y);
   
 }
  
void dfs(int nod, int T, int niv)
 {
    Nod *q;
    low[nod]=df[nod]=niv;
    for(q=prim[nod];q;q=q->urm)
     {
      if ( q->info == T ) continue;
      if ( df[q->info] == -1 )
        {
          st [ 0 ][ ++vf ] = nod; st [ 1 ] [ vf ] = q->info;
          dfs ( q->info , nod , niv+1 );
          if(low[ q->info ] >= low[ nod ] ) elim( nod, q->info );

          low [ nod ] = min ( low[nod],low[ q->info ] );
        }
      else low[nod]=min (low[nod] , df[q->info]);
     }
 }
int main()
 {
 read();
 memset(df,-1,sizeof(df));
 dfs(1,0,0);
 print();
 return 0;
 }