Cod sursa(job #1772494)

Utilizator dodecagondode cagon dodecagon Data 6 octombrie 2016 19:37:30
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <stdio.h>
#include <stdlib.h>
#define min(a,b) ((a)<(b) ? (a) : (b))

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

int n,m,i,j,k=-1,lowlink[100009],index[100009],st[100009],in[100009];
list * g[100009],*p,*cmp[100009];

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

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;
}


void dfs(int x)
{
  index[x]=i;
  lowlink[x]=i;
  i++;
  st[++k]=x;
  in[x]=1;

  
   for (list * p = g[x]; p ;p=p->next)
   	if (index[p->x]==0)
	   {
         dfs(p->x);
         lowlink[x]=min(lowlink[x],lowlink[p->x]);
	   } else 
	   if (in[p->x]==1)
	   	 lowlink[x]=min(lowlink[x],lowlink[p->x]);

   if (index[x]==lowlink[x])
   {
      while (k>=0 && st[k]!=x)
         add(&cmp[j],st[k]),in[st[k]]=0,k--;
       in[x]=0;
      add(&cmp[j],x);
      j++;
   }
}



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

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

    i=1;
    for (i=1;i<=n;++i)
    	if (index[i]==0)
    	  dfs(i);

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

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



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