Rust & Murderer - C++

rust.cc

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_set>
#include <list>
#include <queue>
using namespace std;

void solve(int, int, int, vector<unordered_set<int>>&, vector<int>&);

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    const int INF = INT_MAX >> 2;
    int T, M, N, S;
    cin >> T;
    for (int t = 0; t < T; ++t) {
        cin >> N;
        cin >> M;
        vector<unordered_set<int>> V(N + 1, unordered_set<int>());
        for (int i = 0; i < M; ++i) {
            int u, v;
            cin >> u;
            cin >> v;
            V[u].emplace(v);
            V[v].emplace(u);
        }
        cin >> S;
        vector<int> dist(N + 1, INF);
        solve(M, N, S, V, dist);
        for (int i = 1; i < dist.size(); ++i) {
            if(i != S) {
                cout << dist[i] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

void solve(int M, int N, int S, vector<unordered_set<int>> &V, vector<int> &dist) {
    queue<int> Q;
    list<int> unvisited;
    for (int i = 1; i <= N; ++i) {
        if (i != S) {
            unvisited.emplace_back(i);
        }
    }
    dist[S] = 0;
    Q.emplace(S);
    while (!Q.empty() && !unvisited.empty()) {
        int u = Q.front();
        Q.pop();
        for (auto it = unvisited.begin(); it != unvisited.end();) {
            auto iter = V[u].find(*it);
            if (iter == V[u].end()) {
                dist[*it] = dist[u] + 1;
                Q.emplace(*it);
                it = unvisited.erase(it);
                if (unvisited.empty()) {
                    return;
                }
            } else {
                it++;
            }
        }
    }
}