Nu aveti permisiuni pentru a descarca fisierul grader_test4.in
Cod sursa(job #2377500)
| Utilizator | Data | 10 martie 2019 13:52:12 | |
|---|---|---|---|
| Problema | Sortare topologica | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.79 kb |
#include <bits/stdc++.h>
using namespace std;
#define nmax 50005
int n,m,i,x,y,nod,k;
int sol[50005], gr[50005];
vector <int> G[50005];
queue <int> q;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int main()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
G[y].push_back(x);
gr[x]++;
}
for (i=1;i<=n;i++)
if (gr[i] == 0)
q.push(i);
while(!q.empty())
{
nod = q.front();
sol[++k] = nod;
q.pop();
for (auto &it : G[nod])
{
gr[it]--;
if (gr[it] == 0)
q.push(it);
}
G[nod].clear();
}
for (i=k;i>=1;i--)
g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}
