Submission #1294884


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct UnionFind{
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) r[i]=1,p[i]=i;
  }
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};

signed main(){
  int n,m;
  int MOD=1000000007LL;
  while(cin>>n>>m,n||m){
    UnionFind uf(n);
    for(int i=0;i<m;i++){
      int x,y;
      cin>>x>>y;
      x--;y--;
      uf.unite(x,y);
    }
    int ans=1;
    for(int i=0;i<n;i++) if(uf.find(i)==i) (ans*=2)%=MOD;
    if(m) (ans+=1)%=MOD;
    cout<<ans<<endl;
  }
  return 0;
}

Submission Info

Submission Time
Task D - Everlasting -One-
User beet
Language C++14 (GCC 5.4.1)
Score 100
Code Size 907 Byte
Status AC
Exec Time 253 ms
Memory 1868 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 1
Set Name Test Cases
all Merged
Case Name Status Exec Time Memory
Merged AC 253 ms 1868 KB