Mai intai trebuie sa te autentifici.
Cod sursa(job #2968467)
| Utilizator | Data | 21 ianuarie 2023 09:48:13 | |
|---|---|---|---|
| Problema | Sortare topologica | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.87 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
const int nmax = 5e4+5;
int n,m,a,b;
int grin[nmax];
vector<int>mch[nmax];
vector<int>sol;
int main()
{
fin >> n >> m;
for(int i = 1 ; i <= m ; ++i)
{
fin >> a >> b;
grin[b]++;
mch[a].push_back(b);
}
queue<int>q;
for(int i = 1 ; i <= n ; ++i)
if(grin[i]==0)
{
q.push(i);
sol.push_back(i);
}
while(!q.empty())
{
int crt = q.front();
for(auto it:mch[crt])
{
grin[it]--;
if(!grin[it])
{
q.push(it);
sol.push_back(it);
}
}
q.pop();
}
for(auto it:sol)
fout << it << ' ';
return 0;
}
