Pagini recente » Cod sursa (job #1919101) | Cod sursa (job #1704312) | Cod sursa (job #718154) | Cod sursa (job #2231635) | Cod sursa (job #3199410)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("sortaret.in");
ofstream out("sortaret.out");
#define cin in
#define cout out
#endif // LOCAL
const int nmax = 5e4 + 7;
vector<int> g[nmax]; // graful nostru
vector<int> sortare; // vectorul in care vom retine sortarea topologica
int noduri_in[nmax]; // noduri_in[i] numara cate muchii avem de forma (x -> i)
// adica cate muchii intra in nodul i
int main() {
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
g[a].push_back(b); // adaugam muchia (a -> b), graful fiind directionat
// fiindca avem muchia (a -> b) care intra in b
noduri_in[b] += 1;
}
queue<int> q; // coada in care vom retine nodurile cu grad intern 0 (noduri_in[i] = 0)
for(int i = 1; i <= n; i++) {
if(noduri_in[i] == 0)
q.push(i);
}
while(!q.empty()) {
int nod = q.front(); q.pop();
sortare.push_back(nod); // adaugam nodul in sortare
for(auto vecin : g[nod]) { // pentru fiecare vecin al lui nod
noduri_in[vecin] -= 1; // scadem gradul intern cu 1 (practic, stergem nodul nod)
if(noduri_in[vecin] == 0) // daca gradul intern devine 0
q.push(vecin); // il adaugam in coada
}
}
for(auto nod : sortare) // afisam sortarea topologica
cout << nod << " ";
cout << endl;
}