Submission #73712567

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

struct DSU 
{
    vector<int> parent;
    vector<int> rank;
    DSU (int n) 
    {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for(int i = 1;i <= n;i++)parent[i] = i;
    }
    int find(int x) 
    {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) 
    {
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]) 
        {
            parent[x] = y;
        } 
        else 
        {
            parent[y] = x;
            if(rank[x] == rank[y]) 
            {
                rank[x]++;
            }
        }
    }
};

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<int> U(M + 1),V(M + 1);
    for(int i = 1;i <= M;i++) cin >> U[i] >> V[i];
    vector<long long> pow2(M + 1);
    pow2[0] = 1;
    for(int i = 1;i <= M;i++) pow2[i] = (pow2[i - 1] * 2) % MOD;
    DSU dsu1(N);
    int cnt = N;
    int last_edge = -1;
    for(int i = M;i >= 1;i--) 
    {
        if(cnt == 1) break;
        int u = U[i];
        int v = V[i];
        if(dsu1.find(u) != dsu1.find(v)) 
        {
            dsu1.unite(u,v);
            cnt--;
            if(cnt == 1) 
            {
                last_edge = i;
                break;
            }
        }
    }
    DSU dsu2(N);
    for(int i = M;i >= last_edge + 1;i--) 
    {
        int u = U[i];
        int v = V[i];
        if(dsu2.find(u) != dsu2.find(v)) dsu2.unite(u, v);
    }
    long long ans = 0;
    for(int i = 1;i <= last_edge;i++) 
    {
        int u = U[i];
        int v = V[i];
        if(dsu2.find(u) != dsu2.find(v)) ans = (ans + pow2[i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result