题目链接:http://codeforces.com/contest/789/problem/D
题意:给定一个无向图,可能有自环,无重边,你要求出满足恰好有两条边只走了一次,其它都走了两次的路径数量。两种方案不同当且仅当边不同。 n,m⩽1e6
解法:
先判联通。然后我们把自环和普通边分开考虑。
如果都选普通边,那么这两条边一定要有公共点,用度数计算一下即可。
如果一个选自环,那么显然任意普通边都能成为另一条边。
如果两个都选自环,那么显然没问题。
那么这道题就是一个计数问题了。
//CF 789D
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int maxm = 2*maxn;
int n, m, edgecnt, head[maxn];
struct edge{
int v, nxt;
edge(){}
edge(int v, int nxt) : v(v), nxt(nxt) {}
}E[maxm];
void init(){
memset(head, -1, sizeof(head));
edgecnt = 0;
}
void addedge(int u, int v){
E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;
}
bool vis[maxn], b[maxn];
///vis标记连通块能访问到的,b标记自环
int num = 0, num2 = 0, du[maxn]; //du是记录度数,num记录普通边的边数,num2记录自环的点的数
void dfs(int u)
{
vis[u] = 1;
for(int i = head[u]; ~i; i = E[i].nxt){
int v = E[i].v;
if(vis[v]) continue;
dfs(v);
}
}
int main()
{
init();
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
if(u == v){
b[u] = 1;
num2++;
}
else{
addedge(u, v);
addedge(v, u);
num++;
du[u]++;
du[v]++;
}
}
for(int i = 1; i <= n; i++){
if(b[i] || head[i] != -1){
dfs(i);
break;
}
}
for(int i = 1; i <= n; i++){
if(!vis[i] && (head[i] != -1 || b[i])){
printf("0\n");
return 0;
}
}
long long ans = 0;
for(int i = 1; i <= n; i++){
ans += 1LL*du[i]*(du[i]-1)/2;
}
ans += 1LL*num2*(m-num2) + 1LL*num2*(num2-1)/2;
printf("%lld\n", ans);
return 0;
}