ulvis.paste.net - pastebin

Paste Search Dynamic
Recent pastes
vis
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. const int mod = 1e9 + 7;
  6.  
  7. int m, n, roz;
  8. vector < int > graf [100007];
  9. int vis [100007];
  10. int cykl;
  11.  
  12. void dfs(int u, int ost){
  13.     vis[u] = 1;
  14.     roz++;
  15.     for(int i = 0; i < graf[u].size(); i++){
  16.         int x = graf[u][i];
  17.         if( vis[x] == 1 ){
  18.             if( (x != ost) or ((i > 0) and (graf[u][i - 1] == x)) )
  19.                 cykl++;
  20.         }
  21.         if(vis[x] == 0) dfs(x, u);
  22.     }
  23.     vis[u] = 2;
  24.     return;
  25. }
  26.  
  27. int main(){
  28.     scanf("%d %d",&n,&m);
  29.     for(int i = 1; i <= m; i++){
  30.         int a, b;
  31.         scanf("%d %d",&a,&b);
  32.         graf[a].push_back(b);
  33.         graf[b].push_back(a);
  34.     }
  35.     for(int i = 1; i <= n; i++)
  36.         sort(graf[i].begin(), graf[i].end());
  37.  
  38.     ll wyn = 1LL;
  39.     for(int i = 1; i <= n; i++){
  40.         if(vis[i] == 0){
  41.             cykl = false;
  42.             wyn = wyn % mod;
  43.             roz = cykl = 0;
  44.             dfs(i, i);
  45.  
  46.             if( cykl <= 1 ){ //poprawna spojna, tzn. max jeden cykl
  47.                 if(cykl > 0) wyn *= 2LL;
  48.                 else wyn *= (ll)roz;
  49.             }
  50.             else{
  51.                 wyn = 0LL;
  52.             }
  53.         }
  54.     }
  55.     printf("%lld\n",wyn % mod);
  56.     return 0;
  57. }
Parsed in 0.010 seconds