ABC393C题解

题意

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

思路

简单图指的是没有重边和自环的图，所以在输入

m

条边的时候，判断一下当前边是否为重边或者自环。

自环非常简单，即

u=v

的情况。重边的话用一个 map 记录，因为是无向边，所以当有

u

到

v

的边时也要标记从

v

到

u

的边。

AC Code

CPP

#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;
}

文章操作

题意

思路

AC Code

相关推荐

评论

ABC393C题解