Submission #551733

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

const int MAX = 505050;
const ll MOD = 1e9+7;
int N, M;
ll p2[MAX];
int odd[MAX];
vector<pair<int, ll> > E[MAX];

ll dfs(int v, int pre) {
    ll ret = 0;
    for (auto p : E[v]) if (p.first != pre) {
        ret += dfs(p.first, v);
        if (odd[p.first] == 0) ret += p.second;
        odd[v] ^= odd[p.first];
    }
    return ret % MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    p2[0] = 1;
    ll ret = 0;
    for (int i = 0; i < M; i++) {
        p2[i+1] = (p2[i]*2) % MOD;
        int x, y;
        cin >> x >> y;
        x--; y--;
        (ret += p2[i+1]) %= MOD;
        if (uf.same(x, y)) {
            odd[x] ^= 1;
            odd[y] ^= 1;
        } else {
            uf.unite(x, y);
            E[x].emplace_back(y, p2[i+1]);
            E[y].emplace_back(x, p2[i+1]);
        }
    }
    cout << (ret+dfs(0, -1)) % MOD << endl;
    return 0;
}

Submission Info

Judge Result