1 条题解
-
0xuyifeng LV 10 MOD @ 2017-08-26 19:26:12
-------------------------------------------------AC code-------------------------------------------------
#include<cstdio> #ifdef WIN32 # define outl "%I64d" #else # define outl "%lld" #endif using namespace std; inline int read(){ int x = 0; bool fl = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') fl = 0; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return fl ? x : -x; } /*------------------------------------------------------------------------------------------------------------// 若将双边看做两条边后,图存在欧拉路,则成立 分三种情况讨论: 1、自环都为双边:不考虑自环,剩下的点要构成欧拉路则必须有2个奇点,因为单边连的至少一个点是奇点,易知只有两条 单边连在同一个顶点上时才满足欧拉路,所以 ans += sum{C(d[i], 2)} 2、有且仅有一个自环为单边:取任意一条剩下的非单边非自环作为单边即可满足构成欧拉路,所以 ans += loop*(m-loop) 3、有两个自环为单边:图一定没有奇点,即可构成欧拉回路,所以 ans += C(loop, 2),loop为自环数 //------------------------------------------------------------------------------------------------------------*/ typedef long long LL; const int MAXN = 100005; int n, m, u, v, d[MAXN], loop, fa[MAXN]; LL ans; bool b[MAXN]; int findfa(int x){ if(fa[x] != x) fa[x] = findfa(fa[x]); return fa[x]; } inline void unionn(int x, int y){ fa[findfa(y)] = findfa(x); } inline LL C(int x){//calulate C(x, 2) return 1ll*x*(x-1)>>1; } int main(){ n = read(), m = read(); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++){ u = read(), v = read(); if(u == v) loop++, b[u] = 1; else{ d[u]++, d[v]++; if(findfa(u) != findfa(v)) unionn(u, v); } } int f; for(int i = 1; i <= n; i++) if(b[i] || d[i]){ f = i; break; } f = findfa(f); for(int i = 1; i <= n; i++) if(findfa(i) != f && (b[i] || d[i])) return puts("0"), 0; for(int i = 1; i <= n; i++) ans += C(d[i]);//no loop is one_way edge ans += 1ll*loop*(m-loop); //one loop is one_way edge ans += 1ll*C(loop); //two loops are one_way edge printf(outl, ans); return 0; }
- 1