Pagini recente » Cod sursa (job #1790648) | Cod sursa (job #1041772) | Cod sursa (job #1107638) | Cod sursa (job #2268671) | Cod sursa (job #3199412)
#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
void dfs(int node) {
if(noduri_in[node] != 0) {
// > 0 inseamna ca nu il putem scoate acum fiindca are parinti
// -1 inseamna ca a fost vizitat deja
return;
}
noduri_in[node] = -1; // il vizitam acum
sortare.push_back(node); // il adaugam in sortare
// si il stergem scotand -1 din fiecare nod vecin in care intra
for(auto vecin : g[node]) {
noduri_in[vecin] -= 1;
dfs(vecin);
}
}
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;
}
// De data aceasta vom folosi un DFS
for(int i = 1; i <= n; i++) dfs(i);
// afisam sortarea
for(auto nod : sortare) cout << nod << " ";
cout << "\n";
}