Road blockade

input/code.cpp: In function 'int main()':
input/code.cpp:117:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i=0; i < bridge_tree[u].size(); ++i){
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int index;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<Edge>> adj(n+1, vector<Edge>());
    vector<pair<int, int>> edges(m+1);
    
    for(int i=1; i<=m; ++i){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(Edge{b, i});
        adj[b].push_back(Edge{a, i});
        edges[i] = {a, b};
    }
    
    vector<int> tin(n+1, -1), low(n+1, -1);
    int timer = 0;
    vector<bool> is_bridge(m+1, false);
    
    stack<pair<int, int>> stk;
    stk.push({1, -1});
    
    while(!stk.empty()){
        pair<int, int> current = stk.top();
        stk.pop();
        int u = current.first;
        int parent_edge = current.second;
        if(tin[u] == -1){
            tin[u] = low[u] = ++timer;
            stk.push({u, parent_edge});
            for(auto &edge : adj[u]){
                int v = edge.to;
                int idx = edge.index;
                if(idx == parent_edge) continue;
                if(tin[v] == -1){
                    stk.push({v, idx});
                }
                else{
                    low[u] = min(low[u], tin[v]);
                }
            }
        }
        else{
            for(auto &edge : adj[u]){
                int v = edge.to;
                int idx = edge.index;
                if(idx == parent_edge) continue;
                if(tin[v] < tin[u]){
                    low[u] = min(low[u], tin[v]);
                }
                else{
                    low[u] = min(low[u], low[v]);
                    if(low[v] > tin[u]){
                        is_bridge[idx] = true;
                    }
                }
            }
        }
    }
    
    vector<int> component(n+1, -1);
    int current_component = 0;
    for(int u=1; u<=n; ++u){
        if(component[u] == -1){
            stack<int> s;
            s.push(u);
            component[u] = current_component;
            while(!s.empty()){
                int node = s.top(); s.pop();
                for(auto &edge : adj[node]){
                    int v = edge.to;
                    int idx = edge.index;
                    if(component[v] == -1 && !is_bridge[idx]){
                        component[v] = current_component;
                        s.push(v);
                    }
                }
            }
            current_component++;
        }
    }
    
    int bridge_tree_size = current_component;
    vector<vector<pair<int, int>>> bridge_tree(bridge_tree_size, vector<pair<int, int>>());
    
    for(int i=1; i<=m; ++i){
        if(is_bridge[i]){
            int a = edges[i].first;
            int b = edges[i].second;
            int comp_a = component[a];
            int comp_b = component[b];
            bridge_tree[comp_a].emplace_back(comp_b, i);
            bridge_tree[comp_b].emplace_back(comp_a, i);
        }
    }
    
    int comp1 = component[1];
    int compn = component[n];
    
    queue<int> q;
    vector<int> parent_bridge(bridge_tree_size, -1);
    q.push(comp1);
    
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i=0; i < bridge_tree[u].size(); ++i){
            int v = bridge_tree[u][i].first;
            int bridge_idx = bridge_tree[u][i].second;
            if(parent_bridge[v] == -1){
                parent_bridge[v] = bridge_idx;
                q.push(v);
                if(v == compn){
                    break;
                }
            }
        }
    }
    
    vector<int> S;
    if(comp1 != compn){
        int current = compn;
        while(current != comp1){
            int bridge_idx = parent_bridge[current];
            if(bridge_idx == -1){
                break;
            }
            S.push_back(bridge_idx);
            int a = edges[bridge_idx].first;
            int b = edges[bridge_idx].second;
            int other_comp = (component[a] == current) ? component[b] : component[a];
            current = other_comp;
        }
    }
    
    if(S.empty()){
        cout << "0\n";
        return 0;
    }
    
    if(S.size() ==1){
        cout << S[0] << "\n";
    }
    else{
        bool all_connected_to_n = true;
        int min_bridge_not_connected = INT32_MAX;
        for(auto &road_idx: S){
            int a = edges[road_idx].first;
            int b = edges[road_idx].second;
            if(a != n && b != n){
                all_connected_to_n = false;
                if(road_idx < min_bridge_not_connected){
                    min_bridge_not_connected = road_idx;
                }
            }
        }
        if(all_connected_to_n){
            cout << "0\n";
        }
        else{
            cout << min_bridge_not_connected << "\n";
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: ACCEPTED

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: ACCEPTED

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: ACCEPTED

Test 47

Verdict: WRONG ANSWER

Test 48

Verdict: ACCEPTED

Test 49

Verdict: WRONG ANSWER

Test 50

Verdict: WRONG ANSWER

Test 51

Verdict: WRONG ANSWER

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: WRONG ANSWER

Test 55

Verdict: ACCEPTED

Test 56

Verdict: WRONG ANSWER

Test 57

Verdict: WRONG ANSWER

Test 58

Verdict: ACCEPTED

Test 59

Verdict: WRONG ANSWER

Test 60

Verdict: WRONG ANSWER

Test 61

Verdict: WRONG ANSWER

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: WRONG ANSWER

Test 65

Verdict: WRONG ANSWER

Test 66

Verdict: WRONG ANSWER

Test 67

Verdict: WRONG ANSWER

Test 68

Verdict: ACCEPTED

Test 69

Verdict: WRONG ANSWER