problem

$n$頂点$m$辺の無向グラフが与えられる。多重辺はないが自己辺は含む。 このグラフ上のpathで、$m-2$本の辺をそれぞれ$2$回ずつ通り残る$2$本の辺をそれぞれ$1$回ずつ通るようなpathについて、その種類数を答えよ。 ただし$1$回だけ通る$2$辺からなる集合が同一であるようなpathsは同一視する。

solution

比較的簡単な式で求まる。loopと到達性には気を付ける。$O(n + m)$。

辺が互いに到達可能でなければ明らかに答えは$0$。そうでないとする。 各辺をちょうど$2$回通るような閉路は必ず存在する。これは適当な辺からのDFSを考えればよい。 これにより隣接する$2$辺はなんであれ目的のpathを構成する。 また、loopは任意の辺と共にそのpathを構成できる。 これらは容易に計算できる。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
ll solve(int n, int m, vector<vector<pair<int, int> > > const & mixed_g, vector<vector<int> > const & g, vector<bool> const & has_loop) {
    { // check connectivity
        vector<bool> used(m);
        function<void (int)> go = [&](int i) {
            for (auto edge : mixed_g[i]) {
                int j, eid; tie(j, eid) = edge;
                if (not used[eid]) {
                    used[eid] = true;
                    go(j);
                }
            }
        };
        int root = -1;
        repeat (i,n) {
            if (mixed_g[i].size() != 0) {
                root = i;
                break;
            }
        }
        go(root);
        if (whole(count, used, false)) {
            return 0;
        }
    }
    // count
    int loop_count = whole(count, has_loop, true);
    ll acc = 0;
    repeat (i,n) acc += g[i].size() *(ll) (g[i].size() - 1) / 2;
    acc += loop_count *(ll) (loop_count - 1) / 2;
    acc += loop_count *(ll) (m - loop_count);
    return acc;
}
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<pair<int, int> > > mixed_g(n);
    vector<vector<int> > g(n);
    vector<bool> has_loop(n);
    repeat (eid,m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        if (u == v) {
            mixed_g[u].emplace_back(v, eid);
            has_loop[u] = true;
        } else {
            mixed_g[u].emplace_back(v, eid);
            mixed_g[v].emplace_back(u, eid);
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    // solve
    ll result = solve(n, m, mixed_g, g, has_loop);
    // output
    printf("%lld\n", result);
    return 0;
}