Light rail connections

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

#define int long long
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1001;

int n, m;
set<pii> es;

int par[N], sz[N];
int cc;

int fd (int u) {
    return par[u] == u ? u : par[u] = fd(par[u]);
}

bool unn (int u, int v) {
    u = fd(u), v = fd(v);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    return true;
}

bool check(int uu, int vv) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    cc = n;

    for (auto [u, v] : es) {
        if (u == uu && v == vv) continue;
        if (unn(u, v)) cc--;
    }
    // cerr << cc << '\n';

    return cc == 1;
}

signed main() {
#ifdef LOCAL
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
#endif

    cin >> n >> m;

    vector<set<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        if (u > v) swap(u, v);

        es.insert({u, v});
        adj[u].insert(v);
        adj[v].insert(u);
    }

    int need = 3 * n;
    // need = 7;
    while (sz(es) > need) {
        for (int u = 0; u < n; u++) {
            if (sz(adj[u]) > 3) {
                // cerr << "mm " << u << '\n';
                int curdeg = sz(adj[u]);
                vector<int> will;
                for (int v : adj[u]) {
                    if (sz(adj[v]) == 2 || sz(adj[v]) > 3) {
                        will.push_back(v);
                    }
                }

                for (int v : will) {
                    if (curdeg == 3) break;
                    // cerr << u << ' ' << v << '\n';
                    int uu = u, vv = v;
                    if (uu > vv) swap(uu, vv);
                    // cerr << uu << ' ' << vv << ' ' << check(uu, vv) << '\n';
                    if (check(uu, vv)) {
                        curdeg--;
                        es.erase({uu, vv});
                        adj[uu].erase(vv);
                        adj[vv].erase(uu);
                    }
                }
            }
        }
    }
    assert(check(-1, -1));
    
    cout << sz(es) << '\n';
    for (auto x : es) {
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 6

Verdict: ACCEPTED

Test 7

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 17

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 18

Verdict: RUNTIME ERROR

code: input/code.cpp:99: int main(): Assertion `check(-1, -1)' failed.

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED