Codeforces Round #407 (Div. 2) D. Weird journey
解法
まず,同じ辺を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 食らってしまった.