Why my topo code not working!

[solirous]

Hey, I’m trying to learn toposort, It’s not working
I tried to sumbit on this problem

SPOJ.com - Problem TOPOSORT

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;
}

[tjm]

You can try this test case:

3 3
1 2
2 3
3 1

The expected answer is “Sandro fails.”

[simes]

I’m no expert, but I can’t see how this can give the desired answer. Are you implementing a known algorithm? You might want to take a look at the depth first search section on this wikipedia page.

[jpfr12]

Hi there.
Topologic sort can only be applied on DAGs, so if the graph has cycles, you should return “Sandro fails”. Only after checking if there are no cycles in the graph, you do the topo sort to check if he can do all tasks.