【分类讨论】Codeforces Round #407 (Div. 2) D. Weird journey

考虑这个二元组中有一者是自环,则必然合法。

考虑这两条边都不是自环,如果它们不相邻,则不合法,否则合法。

坑的情况是,如果它是一张完整的图+一些离散的点,则会有解,不要因为图不连通,就误判成无解。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll ans;
int n,m,zihuan;
int v[2000010],next[2000010],first[2000010],e;
void AddEdge(int U,int V){
v[++e]=V;
next[e]=first[U];
first[U]=e;
}
bool vis[2000010];
void dfs(int U){
vis[U]=1;
for(int i=first[U];i;i=next[i]){
if(!vis[v[i]]){
dfs(v[i]);
}
}
}
int main(){
// freopen("d.in","r",stdin);
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
if(x==y){
++zihuan;
}
AddEdge(x,y);
AddEdge(y,x);
}
for(int i=1;i<=n;++i){
if(first[i]){
dfs(i);
break;
}
}
for(int i=1;i<=n;++i){
if((!vis[i]) && first[i]){
puts("0");
return 0;
}
}
ans=(ll)(zihuan-1)*(ll)(zihuan)/2ll+(ll)zihuan*(ll)(m-zihuan);
for(int i=1;i<=n;++i){
int cnt=0;
for(int j=first[i];j;j=next[j]){
if(v[j]!=i){
++cnt;
}
}
ans+=(ll)cnt*(ll)(cnt-1)/2ll;
}
cout<<ans<<endl;
return 0;
}
上一篇:【预处理】Codeforces Round #407 (Div. 2) C. Functions again


下一篇:【贪心】Codeforces Round #407 (Div. 2) A. Anastasia and pebbles