CFR 788 B. Weird journey ( Euler's Path, Ad hoc )

Problem - B - Codeforces

題意：
給一個 N 點 M 邊的無向圖，問有幾種方法，可以經過 M - 2 個邊洽兩次，剩下 2 個邊洽一次。沒有重邊，但可能有自環。兩個方法不同，若且唯若拜訪洽一次的任意一邊不同。

資料規模：
The first line contains two integers n, m (1 ≤ n, m ≤ 1e6) — the number of cities and roads in Uzhlyandia, respectively.
Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) that mean that there is road between cities u and v.
It is guaranteed that no road will be given in the input twice. That also means that for every city there is no more than one road that connects the city to itself.

解法：
先考慮無自環。有點顯然，恰被拜訪一次的那兩個邊必然是共享一個端點。
接著考慮自環，可以發現自環可以洽走一次，裝得好像跟沒走一樣。
因此先數自環的數量，並只給非自環的邊的端點添上度數。
答案是所有點的 C( 度數, 2 )，加上非自環邊數量乘上自環數量，加上 C( 自環數量, 2 )。

時間 / 空間複雜度：
O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;

int N, M;
int deg[ MAXN ];
int vis[ MAXN ];
int sl; // self loop

int fa[ MAXN ];
int find( int x ){
  return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
void unite( int x, int y ){
  int a = find( x );
  int b = find( y );
  fa[ a ] = b;
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> M;
    for( int i = 0; i < N; ++i ){
      fa[ i ] = i;
    }
    for( int i = 0; i < M; ++i ){
      int u, v;
      cin >> u >> v;
      --u, --v;
      vis[ u ] = vis[ v ] = 1;
      if( u == v ){
        ++sl;
      } else{
        ++deg[ u ];
        ++deg[ v ];
        unite( u, v );
      }
    }
    set< int > bag;
    for( int i = 0; i < N; ++i ){
      if( not vis[ i ] ) continue;
      bag.emplace( find( i ) );
    }
    if( bag.size() > 1 ){
      cout << "0\n";
      exit( 0 );
    }
  }
  {
    long long ans = 0LL;
    int ecnt = 0;
    for( int i = 0; i < N; ++i ){
      ans += 1LL * deg[ i ] * ( deg[ i ] - 1 ) / 2;
      ecnt += deg[ i ];
    }
    ecnt /= 2;
    ans += 1LL * ecnt * sl;
    ans += 1LL * sl * ( sl - 1 ) / 2;
    cout << ans << endl;
  }
  return 0;
}