题目链接: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;
}