1 / 4
Jun 2024

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

    Jun '24
  • last reply

    Jun '24
  • 3

    replies

  • 240

    views

  • 4

    users

  • 2

    likes

  • 2

    links

You can try this test case:

3 3
1 2
2 3
3 1

The expected answer is “Sandro fails.”

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 page2.

12 days later

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.