Codeforces Round #407 (Div. 2) D. Weird journey

問題文

http://codeforces.com/contest/789/problem/D

解法

まず，同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます．
自己辺を考えるのはめんどうなので，とりあえずない場合を考えると，条件を満たすパスがあるかどうかは，「一度のDFSによって辿れる頂点の次数の総和が，辺の個数 m の2倍になっている」ことと同値である（よね？）とわかります．
この時，隣接する任意の2つの辺について，それら2つを1回だけ通り，その他の辺を2回通るパスが明らかに存在します．
なので，この隣接する2辺のペアを適当に求めます（1つの頂点に着目して，出てる辺から2つ選べば良いです）．
最後に自己辺ですが，まあ実験すればすぐわかるんですけど，こいつらは自由に使えます．
なので，最後に 自己辺の数 * (自己辺を除くその他の辺) + (自己辺から2つ選ぶ選び方) を足してやれば解けます．

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

using graph = vector<vector<int>>;

int dfs(graph const& g, int v, int p, vector<bool>& used) {
    int res = g[v].size();
    used[v] = true;
    for(auto to : g[v]) {
        if(to == p || used[to]) {
            continue;
        }
        res += dfs(g, to, v, used);
    }
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    graph g(n);
    int root = -1;
    vector<vector<int>> v(n);
    int self_cnt = 0;
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        root = a;
        if(a == b) {
            g[a].push_back(a);
            self_cnt++;
        } else {
            g[a].push_back(b);
            g[b].push_back(a);
            v[a].push_back(i);
            v[b].push_back(i);
        }
    }

    vector<bool> used(n);
    if(dfs(g, root, -1, used) + self_cnt != 2 * m) {
        printf("0\n");
    } else {
        ll res = 0;
        for(auto x : v) {
            if(x.size() != 0) {
                res += x.size() * (x.size() - 1) / 2;
            }
        }
        res += self_cnt * (m - self_cnt);
        res += self_cnt * (self_cnt - 1) / 2;
        printf("%lld\n", res);
    }
}

感想

あくまで辺を頂点と見たグラフが連結であればよいので，頂点自体が連結である必要はないです（罠）．
あと入力が 10^6 だったのを忘れて cin で TLE 食らってしまった．