AT_abc393_c 题解

getchar_unlocked · 2025-02-17 21:07:21 · 题解

题目传送门

思路

首先判断自环情况 u=v，多余的这条边一定时需要删除的，故将答案增加 1 即可。

然后用一个 map 存储所有边，如果存在重复的边。存储完后进行遍历，有多少重边就要删去。

最后输出上述两次的总和即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10;
unordered_map<int,int>mp;
signed main(){
    int n=read(),m=read();
    int sum=0;
    while(m--){
        int u=read(),v=read();
        if(u==v)
            ++sum;
        else{
            if(u>v)
                swap(u,v);
            ++mp[u*(n+1)+v];
        }
    }
    int ans=0;
    for(auto i:mp)
        ans+=i.second-1;
    printf("%lld\n",ans+sum);
    return 0;
}