Mai intai trebuie sa te autentifici.

Cod sursa(job #2204583)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 16 mai 2018 17:20:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <vector>
using namespace std;
FILE *f,*g;

vector<int> a[50002];

int n,m;
int deg[50002], q[50002];

void read()
{
  fscanf(f,"%d %d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int x,y;
    fscanf(f,"%d %d",&x,&y);
    a[x].push_back(y);
    deg[y]++;
  }
}

void top_sort()
{    vector<int>::iterator j;
    for(int ii=1;ii<=n;ii++)
        if(!deg[ii])
            q[++q[0]]=ii;

    for(int i=1;i<=n;i++)
    {
        int node=q[i];
        for(j=a[node].begin(); j!=a[node].end(); ++j)
        {
            deg[*j]--;
            if(deg[*j]==0)
                q[++q[0]]=*j;
        }
    }
}
void write()
{
    for(int i=1; i<=n; i++)
        fprintf(g,"%d ",q[i]);
}
int main()
{
    f=fopen("sortaret.in","r");
    g=fopen("sortaret.out","w");
    read();
    top_sort();
    write();
    return 0;
}