Hey, I’m trying to learn toposort, It’s not working
I tried to sumbit on this problem
and it just WA
What I tried:
I tried to visualize the graph, and figuring out by myself however I really can’t
here’s my code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int n, m;
vector<int> adj[maxn];
vector<bool> visited;
vector<int> ans;
map<pair<int, int>, bool> ck;
void dfs(int v) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u])
dfs(u);
}
ans.push_back(v);
}
void topological_sort() {
visited.assign(n + 1, false);
ans.clear();
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i);
}
}
reverse(ans.begin(), ans.end());
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int v1, v2;
cin >> v1 >> v2;
adj[v1].push_back(v2);
ck[{v1, v2}] = true;
}
for (auto& [key, val] : ck) {
int v1 = key.first, v2 = key.second;
if (ck.find({v2, v1}) != ck.end()) {
cout << "Sandro fails." << '\n';
return 0;
}
}
topological_sort();
for (int c : ans) {
cout << c << " ";
}
return 0;
}
created
last reply
- 3
replies
- 240
views
- 4
users
- 2
likes
- 2
links