【题目链接】:http://codeforces.com/problemset/problem/789/D
【题意】
给你n个点,m条边;
可能会有自环
问你有没有经过某两条边各一次,然后剩余m-2条边,每条边各2次的
遍历方案,有的话输出方案数
【题解】
/*
把每条边都复制一条相同的边;
然后问题就能转化为在2*m条边中,去掉两条边;
然后使得剩下的图能够进行一笔画(每条边都只经过一次)
则使奇点的个数为0或为2就好了;
考虑自环边和普通边;
对于普通边来说:
①如果删掉的两条普通边是不相邻的两条边;
那么会有4个点变成奇点->排除
②如果删掉的两条普通边是相邻的两条边
则x-y-z中x和z会变成奇点;y仍旧是偶点;
刚好形成了两个奇点->符合要求
③考虑两条不同的自环边,如果删掉之后
每条自环边的端点两边都是同一个点,则每个点度数都减少2；
则每个点还都是偶点->奇点个数为0->符合
④一条自环边和一条普通边
普通边两边的点都变成奇点
->自环边两边的点是同一个点那个点度数-2还是偶点;
->总共两个奇点
还是符合题意
综上只要考虑
自环边和自环边
相邻的普通边
自环边和普通边
3种情况
如果没有联通的话得输出0
这里的联通只考虑m条边中出现过的点哦;
只要那些点联通就可以了【Number Of WA】
3
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e6+100;
int n,m,ltk;
int f[N];
LL zh,ptb,ans,bian[N];
bool bo[N];
int zbb(int x)
{
if (f[x]==x)
return x;
else
return f[x] = zbb(f[x]);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf就别用了!
cin >> n >> m;
ltk = n;
rep1(i,1,n) f[i] = i;
rep1(i,1,m)
{
int x,y;
cin >> x >> y;
bo[x] = true,bo[y] = true;
if (x==y)
{
zh++;
continue;
}
ptb++;
bian[x]++,bian[y]++;
int r1 = zbb(x),r2 = zbb(y);
if (r1!=r2)
{
ltk--;
f[r1] = r2;
}
}
rep1(i,1,n)
if (!bo[i])
ltk--;
if (ltk!=1)
return cout << 0 << endl,0;
//自环和自环
ans+=zh*(zh-1)/2;
//自环和普通边
ans+=zh*ptb;
//相邻的普通边
rep1(i,1,n)
ans+=bian[i]*(bian[i]-1)/2;
cout << ans << endl;
return 0;
}