Codeforces Round #407 (Div. 1): B. Weird journey
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;
}