Cod sursa(job #2287796)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 noiembrie 2018 15:25:03
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
int n,m,i,j,a,b,l[100001],w[50001],g[50001],q[50001],k;
int main() {
    freopen("sortaret.in","r",stdin),freopen("sortaret.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d",&a,&b),w[a]++;
    for(i=1;i<=n;i++)
        w[i]+=w[i-1];
    fclose(stdin);
    freopen("sortatet.in","r",stdin),scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d",&a,&b),q[a]++,l[w[a-1]+q[a]]=b,g[b]++;
    for(i=1;i<=n;i++)
        q[i]=0;
	for(i=1;i<=n;i++)
		if(!g[i])
			q[++q[0]]=i;
	for(i=1;i<=q[0];i++) {
		k=q[i],printf("%d ",k);
		for(j=w[k-1]+1;j<=w[k];j++) {
			g[l[j]]--;
			if(!g[l[j]])
				q[++q[0]]=l[j];
		}
	}
}
/*#include <stdio.h>
int n,m,i,j,a,b,list[100001],nr[50001],grad[50001],q[50001],k,t;
int main() {
	freopen("sortaret.in","r",stdin),freopen("sortaret.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d",&a,&b),nr[a]++;
	for(i=1;i<=n;i++)
		nr[i]+=nr[i-1];
	fclose(stdin);
	freopen("sortaret.in","r",stdin),scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) {
		scanf("%d%d",&a,&b);
		q[a]++;
		list[nr[a-1]+q[a]]=b;
		grad[b]++;
	}
	for(i=1;i<=n;i++)
		q[i]=0;
	for (i = 1; i <= n; i++) {
		if (grad[i] == 0) {
			q[0]++;
			q[q[0]] = i;
		}
	}
	i = 1;
	while (i <= q[0]) {
		t = q[i];
		printf("%d ", t);
		for (j = nr[t - 1] + 1; j <= nr[t]; j++) {
			grad[list[j]]--;
			if (grad[list[j]] == 0) {
				q[0]++;
				q[q[0]] = list[j];
			}

		}
		i++;
	}
	return 0;
}*/