Cod sursa(job #2768836)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 12:46:48
Problema Componente tare conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
int n,m,w[N],*g[N],i,d,c[N],l[N],r,a[2*N],b[2*N],v[N],s[2*N],q[2*N],u,t;
void T(int i)
{
	int k,j,o;
	s[++t]=i,v[i]=!v[i]?1:v[i],l[i]=c[i]=d++;
	for(j=0;j<w[i];j++)
        if(!c[g[i][j]]) {
            T(g[i][j]);
            if(l[i]>l[g[i][j]])
                l[i]=l[g[i][j]];
        } else if(v[g[i][j]]==1&&l[i]>c[g[i][j]])
            l[i]=c[g[i][j]];
	if(c[i]==l[i]) {
      	for(k=0,r++;t;) {
            o=s[t--];
            if(o==i||v[o]!=1)
                break;
            q[++u]=o,k++,v[o]=2;
        }
      	if(v[i]==1)
            v[i]=2,k++,q[++u]=i;
      	if(!k)
            r--;
      	else
            q[++u]=0;
	}
}
int main()
{
	freopen("ctc.in","r",stdin),freopen("ctc.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
    	scanf("%d%d",a+i,b+i),w[a[i]]++;
	for(i=1;i<=n;w[i++]=0)
      	g[i]=(int*)malloc(4*w[i]);
	for(i=1;i<=m;++i)
      	g[a[i]][w[a[i]]++]=b[i];
	for(i=1;i<=n;++i)
        if(!c[i])
            T(i);
    for(printf("%d\n",r),--u;u;--u)
        if(!q[u])
            printf("\n");
        else
            printf("%d ",q[u]);
    return 0;
}