Mai intai trebuie sa te autentifici.
Cod sursa(job #1327075)
| Utilizator | Data | 26 ianuarie 2015 12:55:46 | |
|---|---|---|---|
| Problema | Sortare topologica | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.21 kb |
#include <stdio.h>
#include <vector>
std::vector<int> *adj;
int in[50001],a[50001];
int n,m;
bool fol[50001];
int main()
{
freopen ("sortaret.in","r",stdin);
freopen ("sortaret.out","w",stdout);
scanf("%d%d",&n,&m);
adj=new std::vector<int> [n+1];
int p1,p2;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p1,&p2);
in[p2]++;
adj[p1].push_back(p2);
}
int pos=1;
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
a[pos]=i;
fol[i]=1;
pos++;
}
}
for(int i=1;i<pos;i++)
{
while(!adj[a[i]].empty())
{
in[adj[a[i]].back()]--;
if(in[adj[a[i]].back()]==0)
{
a[pos]=adj[a[i]].back();
pos++;
}
adj[a[i]].pop_back();
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
