ABC393C题解

Lovely_yhb · 2025-02-16 08:17:32 · 题解

题意

给你一张无向图，问最少删几条边能使它变成一张简单图。

思路

简单图指的是没有重边和自环的图，所以在输入 m 条边的时候，判断一下当前边是否为重边或者自环。

自环非常简单，即 u=v 的情况。重边的话用一个 map 记录，因为是无向边，所以当有 u 到 v 的边时也要标记从 v 到 u 的边。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,ans=0,u,v;
map<int,bool> vis[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        if(u==v||vis[u][v]||vis[v][u]) ans++;
        vis[u][v]=1,vis[v][u]=1;
    }
    cout<<ans;
    return 0;
}