Tunnels

#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <tuple>

#define long long long

using namespace std;

typedef pair<int, int> pii;

int N, M;
int pos;
vector<set<int>> adj;
vector<priority_queue<pii>> adj2;
vector<int> order;
vector<int> ordpos;
vector<bool> visited;

void dfs(int i) {
    if (visited[i]) return;
    visited[i] = true;
    for (int other: adj[i]) {
        dfs(other);
    }
    order[pos] = i;
    ordpos[i] = pos;
    pos--;
}

void dfs2(int i) {
    if (adj2[i].size() == 0) {
        return;
    }
    pii other = adj2[i].top();
    adj2[i].pop();
    dfs2(other.second);
}

int main() {
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    adj = vector<set<int>> (N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a-1].insert(b-1);
    }

    order = vector<int> (N, -1);
    ordpos = vector<int> (N, -1);
    visited = vector<bool> (N, false);
    pos = N-1;
    for (int i = 0; i < N; i++) {
        dfs(i);
    }

    adj2 = vector<priority_queue<pii>> (N);
    for (int i = 0; i < N; i++) {
        for (int other: adj[i]) {
            adj2[i].push(pii(ordpos[other], other));
        }
    }

    int result = 0;
    for (int i = 0; i < N; i++) {
        int node = order[i];
        while (adj2[node].size() > 0) {
            dfs2(node);
            result++;
        }
    }
    cout << result << "\n";


    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED