题意:
给出无向图.
good way : 仅有两条边只经过一次,余下边全经过两次的路
问你共有多少条不同的good way。
两条good way不同仅当它们所经过的边的集合中至少有一条不同 (很关键)
存在多个边连通分量的情况肯定是0.
当确定某两条边只经过一次的时候:
由于经过边的顺序不重要,余下边全经过两次,至多只有一条good way
那么把剩下经过两次的边拆分成两条经过一次的边,记现在的图是新图
原图中是否存在good way 就等价于新图中是否存在欧拉路
暴力枚举两条边判断肯定是要TLE的
那就要考虑怎样的两条边存在解
先不考虑自环:
当这两条边不相邻时:
由于只有这两条边的端点的度是奇数,其他点都是偶数,新图中共有四个点是奇数度,不存在欧拉路
当这两条边相邻时:
这两条边的三个端点中两个是奇数,余下都是偶数,存在欧拉回路
考虑自环
当其中有一条边是自环时:
自环只有一个端点,故自环的端点是偶数度,新图中只有两个奇数度点,存在欧拉回路
当两条边都是自环时:
所有点都是偶数度,存在欧拉回路
故存在解的情况:
两条边相邻 (去掉自环后的边):
枚举每个端点i, ans += Comb(edge[i].size(), 2);
其中一条边是自环:
ans += loopCnt * (m-1);
ans -= Comb(loopCnt, 2);//重复计算
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int MAXN = 1000005; 5 int n, m; 6 vector<int> G[MAXN]; 7 int loop[MAXN], lcnt; 8 int vis[MAXN]; 9 void dfs(int x) 10 { 11 if (vis[x]) return; 12 vis[x] = 1; 13 for (int i = 0; i < G[x].size(); i++) 14 dfs(G[x][i]); 15 } 16 int main() 17 { 18 for (int i = 1; i <= n; i++) 19 G[i].clear(), vis[i] = loop[i] = 0; 20 lcnt = 0; 21 scanf("%d%d", &n, &m); 22 int root; 23 for (int i = 1; i <= m; i++) 24 { 25 int x, y; scanf("%d%d", &x, &y); 26 if (x == y) loop[x]++ ,lcnt++; 27 else 28 { 29 G[x].push_back(y); 30 G[y].push_back(x); 31 } 32 root = x; 33 } 34 dfs(root); 35 bool flag = 1; 36 for (int i = 1; i <= n; i++) 37 { 38 if (!vis[i] && (G[i].size() || loop[i])) 39 flag = 0; 40 } 41 if (!flag) 42 { 43 puts("0"); return 0; 44 } 45 LL ans = 0; 46 for (int i = 1; i <= n; i++) 47 { 48 int sz = G[i].size(); 49 ans += (LL)sz*(sz-1) / 2; 50 } 51 ans += (LL)lcnt * (m-1); 52 ans -= (LL)lcnt * (lcnt-1) / 2; 53 printf("%lld ", ans); 54 }