Cod sursa(job #1472469)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 08:54:40
Problema Componente tare conexe Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
int n,m,w[100001],*g[100001],i,d,c[100001],l[100001],r,a[200002],b[200002],v[100001],s[200002],q[200002],t,u;
void T(int i) {
	int k,j;
	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;q[++u]=s[t],k++,v[s[t--]]=2)
        if(s[t]==i||v[s[t]]!=1)
            break;
      	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(w[i]*sizeof(int));
	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);
	printf("%d\n",r);
	for(u--;u;u--)
	if(!q[u])
		printf("\n");
	else
		printf("%d ",q[u]);
}