Submission #338106

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
int par[400000];
void init(int n){rep(i,n) par[i]=i;}
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
void unite(int x,int y){
	x=find(x),y=find(y);
	par[x]=y;
}
struct edge{int c,a,b;};
bool comp(const edge& x,const edge& y){
	return x.c<y.c;
}
int deg[400000];
bool od[400000];
typedef long long ll;
typedef pair<int,int> P;
ll ans=0,mod=1e9+7,p2[500001];
vector<P> G[400000];
vector<edge> es;
void dfs(int v,int pre){
	bool ev=(deg[v]%2==0);
	for(P p:G[v]){
		int u=p.fs;
		if(u==pre) continue;
		dfs(u,v);
		if(od[u]){
			ev=!ev;
			ans+=p2[p.sc];
			ans%=mod;
		}
	}
	od[v]=!ev;
}
int main(){
	int N,M;
	cin>>N>>M;
	p2[0]=1;
	rep(i,M) p2[i+1]=p2[i]*2%mod;
	init(N);
	rep(i,M){
		int a,b;
		cin>>a>>b;
		es.pb({i+1,a-1,b-1});
		deg[a-1]++;
		deg[b-1]++;
	}
	sort(all(es),comp);
	for(edge e:es){
		if(same(e.a,e.b)) continue;
		unite(e.a,e.b);
		G[e.a].pb(P(e.b,e.c));
		G[e.b].pb(P(e.a,e.c));
	}
	dfs(0,-1);
	rep1(i,M) ans+=p2[i],ans%=mod;
	cout<<ans<<endl;
}

Submission Info

Judge Result