Cod sursa(job #1775131)

Utilizator dodecagondode cagon dodecagon Data 9 octombrie 2016 21:53:06
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <stdio.h>
#include <stdlib.h>


const int buff_size=4096;
char buff[buff_size];
int _i=buff_size;


int next_int(FILE * in)
{
    char x,y,k=1;
    int z=0;
   
   if (_i==buff_size)
    y=fread(buff,buff_size,1,in),_i=0;
      
     x=1;
 
      while ((x<48 || x> 57) && x!='-')
         {  
          x=buff[_i];
          _i++;
          if (_i==buff_size)
             {
              y=fread(buff,buff_size,1,in);
              _i=0;
             }
         }
 
      while (x>=48 && x<=57 || x=='-')
      {
        if (x=='-') 
          k=-1; else 
        z=(z<<1)+(z<<3)+x-48;
        x=buff[_i];
        _i++;
         if (_i==buff_size)
           {
               y=fread(buff,buff_size,1,in);
               _i=0;
             }
      }
 
    return z*k;
}


struct list 
{
	int x;
	list * next;
};

list * g[100009], * sol[100009],*p;
int st[100009],lowlink[100005],index[100009],n,m,x,y,z,i,j,k;


void add(list **l,int x)
{
   p=(list *) malloc(sizeof(list));
   p->next=*l;
   p->x=x;
   *l=p;
}

void dfs(int v,int to)
{
	lowlink[v]=index[v]=i++;
	st[++k]=v;
    list * p;
	for (p=g[v]; p ; p=p->next)
	{
		if (v==to) continue;
		if (index[p->x]==0)
		{
		  int f=k;
          dfs(p->x,v);

          lowlink[v]=(lowlink[v] < lowlink[p->x] ? lowlink[v] : lowlink[p->x]);

          if (lowlink[p->x]>=index[v])
          {
             j++;
          	while (st[k]!=v)
             add(&sol[j],st[k--]);
            add(&sol[j],v);
          }
		} else 
		 lowlink[v]=(lowlink[v] < index[p->x] ? lowlink[v] : index[p->x]);

	}
}

int main(int argc, char const *argv[])
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
     
     n=next_int(stdin);
     m=next_int(stdin);

      while (m--)
      {
      	x=next_int(stdin);
      	y=next_int(stdin);
      	add(&g[x],y);
      	add(&g[y],x);
      }

      i=20;

      dfs(1,-1);

      printf("%d\n",j);

      for (i=1;i<=j;++i)
      {
      	for (p=sol[i]; p ;p=p->next)
      		printf("%d ",p->x);
      	puts("");
      }


	fclose(stdin);
	fclose(stdout);
	return 0;
}