Mai intai trebuie sa te autentifici.
Cod sursa(job #2204583)
Utilizator | 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;
}