Submission #353894

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
typedef int Weight;
struct Edge{
    int src,dst;
    Weight weight;
    int rev;
    Edge(int f, int t, Weight c=1, int rev=0):src(f),dst(t),weight(c),rev(rev){}
    bool operator < (const Edge& re)const{ return weight > re.weight;}
};
typedef vector< vector<Edge> > Graph;
void add_edge(Graph &G, int s, int t, Weight cap){
    G[s].push_back(Edge(s, t, cap, G[t].size()));
    G[t].push_back(Edge(t, s, cap, G[s].size()-1));
}
typedef vector<Edge> Edges;
pair<Weight, Edges> minimumSpanningForest(const Graph &g) {
    int n = g.size();
    UnionFind uf(n);
    priority_queue<Edge> Q;
    REP(u, n) FOR(e, g[u]) if (u < e->dst) Q.push(*e);
    Weight total = 0;
    Edges F;
    while (F.size() < n-1 && !Q.empty()) {
        Edge e = Q.top(); Q.pop();
        if (uf.unionSet(e.src, e.dst)) {
            F.push_back(e);
            total += e.weight;
        }
    }
    return pair<Weight, Edges>(total, F);
}

int dfs(int pre, int v, vector<vi> &g, vi &even, vi &evennum){
    int res = 0;
    if(even[v]) res++;
    if(pre != -1 && g[v].size() == 1) return res;
    FOR(e, g[v]){
        if((*e) == pre) continue;
        res += dfs(v, *e, g, even, evennum);
    }
    evennum[v] = res;
    return res;
}



int main(void){
    int N, M;
    cin >> N >> M;
    vector<pii> e;
    vector<ll> cost(M, 2);
    for(int i = 1; i < M; i++) (cost[i] = cost[i-1] * 2) %= MOD;
    ll ans = 0LL;
    vi even(N, 0);
    Graph g(N);
    REP(i, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        e.push_back(make_pair(a, b));
        even[a]++; even[b]++;
        ans = (ans + cost[i]) % MOD;
        add_edge(g, a, b, i);
    }
    REP(i, N) even[i] %= 2; 
    pair<Weight, Edges> msf = minimumSpanningForest(g);
    
    int evensum = 0;
    Edges es = msf.second;
    vi evennum(N, 0);
    vector<vi> gs(N);
    FOR(e, es){
        int x = (*e).src, y = (*e).dst;
        gs[x].push_back(y);
        gs[y].push_back(x);
    }
    
    evensum = dfs(-1, 0, gs, even, evennum);
    RREP(i, es.size()){
        //cout << es[i].src << "*" << es[i].dst << ":" << es[i].weight << endl;
        int x = es[i].src, y = es[i].dst;
        int k = min(evennum[x], evennum[y]);
        if(k % 2 == 1 || (evensum - k) % 2 == 1){
            ans = (ans + cost[es[i].weight]) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result