Submission #73718098

---

Source Code Expand

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

struct DSU {
    vector<int> parent, sz;
    int forests;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        forests = n;
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.resize(n + 1, 1);
    }

    int getRoot(int u) {
        if(u == parent[u]) return u;
        return parent[u] = getRoot(parent[u]);
    }

    bool same(int u, int v) {
        return getRoot(u) == getRoot(v);
    }

    bool join(int u, int v) {
        u = getRoot(u), v = getRoot(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        parent[v] = u;
        forests--;
        return true;
    }

    int compSize(int u) {
        return sz[getRoot(u)];
    }
};

const int MOD = 998244353;
int fp(int n, int p) {
    int res = 1;
    while (p) {
        if (p & 1) res = 1LL * res * n % MOD;
        n = 1LL * n * n % MOD;
        p >>= 1;
    }
    return res;
}

void O_O() {
    int n, m, ans = 0;
    cin >> n >> m;

    vector<array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i][1] >> edges[i][2];
        edges[i][0] = i + 1;
    }
    sort(edges.rbegin(), edges.rend());

    DSU dsu(n);
    for (auto& [i, u, v] : edges) {
        bool same = dsu.same(u, v);
        if (!same && dsu.forests == 2) {
            ans += fp(2, i);
            if (ans >= MOD) ans -= MOD;
        } else {
            dsu.join(u, v);
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC
    while (TC--) {
        O_O();
        if (TC) cout << '\n';
    }

    return 0;
}

Submission Info

Judge Result