Codeforces 788B 想法+并查集

90 阅读 0 评论 60 点赞

我是靠谱客的博主欢喜月饼，最近开发中收集的这篇文章主要介绍Codeforces 788B 想法+并查集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia.

It is widely known that Uzhlyandia has n cities connected with m bidirectional roads. Also, there are no two roads in the country that connect the same pair of cities, but roads starting and ending in the same city can exist. Igor wants to plan his journey beforehand. Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once. The good path can start and finish in any city of Uzhlyandia.

Now he wants to know how many different good paths are in Uzhlyandia. Two paths are considered different if the sets of roads the paths goes over exactly once differ. Help Igor — calculate the number of good paths.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 106) — the number of cities and roads in Uzhlyandia, respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) that mean that there is road between cities u and v.

It is guaranteed that no road will be given in the input twice. That also means that for every city there is no more than one road that connects the city to itself.

Output

Print out the only integer — the number of good paths in Uzhlyandia.

Examples

input
5 4
1 2
1 3
1 4
1 5

output
6

input
5 3
1 2
2 3
4 5

output
0

input
2 2
1 1
1 2

output
1

Note

In first sample test case the good paths are:

2 → 1 → 3 → 1 → 4 → 1 → 5,
2 → 1 → 3 → 1 → 5 → 1 → 4,
2 → 1 → 4 → 1 → 5 → 1 → 3,
3 → 1 → 2 → 1 → 4 → 1 → 5,
3 → 1 → 2 → 1 → 5 → 1 → 4,
4 → 1 → 2 → 1 → 3 → 1 → 5.

There are good paths that are same with displayed above, because the sets of roads they pass over once are same:

2 → 1 → 4 → 1 → 3 → 1 → 5,
2 → 1 → 5 → 1 → 3 → 1 → 4,
2 → 1 → 5 → 1 → 4 → 1 → 3,
3 → 1 → 4 → 1 → 2 → 1 → 5,
3 → 1 → 5 → 1 → 2 → 1 → 4,
4 → 1 → 3 → 1 → 2 → 1 → 5,
and all the paths in the other direction.

Thus, the answer is 6.

In the second test case, Igor simply can not walk by all the roads.

In the third case, Igor walks once over every road.

题意：给你n个点 m条边问你有多少种方法 m-2条边经过两次剩余2条边经过一次有自环但没有重边

题解：

首先判掉图不连通的情况并查集搞一搞就行了

假设自环有now个那么答案首先加上 now*(now-1)/2 代表找出来两个自环走一次剩余的边全走两次

然后是对于每个点假设当前点有n条边(不含自环) 那么一条边一个自环的情况就是 n*now

两条边的情况就是 n*(n-1)/2

因为一条边一个自环的情况会多算一次所以要除2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[1000005],pre[1000005],ps[1000005];
int find(int x){
int r=x;
while(pre[r]!=r)
r=pre[r];
int i=x,j;
while(i!=r){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void link(int a,int b){
if(find(a)!=find(b))pre[find(a)]=find(b);
}
int main(){
ll x,y,n,m,i,j,xi,ans1=0,ans2=0,now=0,p;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)pre[i]=i;
for(i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
link(x,y);
p=x;
if(x!=y){
a[x]++;
a[y]++;
}
else now++;
ps[x]++;
ps[y]++;
}
for(i=1;i<=n;i++){
if(find(pre[i])!=find(pre[x])&&ps[i]){
printf("0n");
return 0;
}
}
ans1=now*(now-1)/2;
for(i=1;i<=n;i++){
ans1+=a[i]*(a[i]-1)/2;
ans2+=now*a[i];
}
printf("%lldn",ans1+ans2/2);
return 0;
}