caioj:1093: 并查集2(scy的删边问题) C++
2024-08-29 20:49:37
题目描述
【题目描述】
读入一个无向图(可能含有多个连通分支),输出最多能删掉多少条边,而不改变这个图任意两点的连通性(原来连通的两个点依然连通,不连通的依然不连通)。
【输入格式】
第一行为图的顶点数N(1≤N≤1000)和边数M(0≤M ≤(N*(N+1)/2) ),它们之间用一个空格隔开,图中的顶点用1到N的整数标号。
接下来的M行,每行用两个数v1和v2表示一条边。v1和v2用一个空格隔开,表示这条边所连接的顶点的标号(v1≠v2),同一条边不会重复出现。
【输出格式】
输出最多能删掉的边数。
输入
输出
样例输入
5 7 4 5 1 2 1 3 1 4 2 3 2 4 3 4
样例输出
3
题解:n个点只用保留n-1条边,只要用m-(n-1)就行了
代码:
#include<cstdio>
using namespace std;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
}
printf("%d\n",m-n+);
return ; }
注:上面的图片侵权抱歉!
最新文章
- BZOJ4591——[Shoi2015]超能粒子炮&#183;改
- 【Java EE 学习 17 下】【数据库导出到Excel】【多条件查询方法】
- 【HOW】如何限制Reporting Services报表导出功能中格式选项
- Tomcat中JVM内存溢出及合理配置
- GJM :JS + CSS3 打造炫酷3D相册 [转载]
- Java设计模式学习笔记(观察者模式)
- Callable接口、Runable接口、Future接口
- Step By Step(Lua字符串库) (转)
- struts2 jsp表单提交后保留表单中输入框中的值 下拉框select与input
- Python Paste.deploy 笔记
- 45种Javascript技巧大全【转藏】
- zoj 3819 Average Score
- node.js第二天之模块
- hadoop2.6.0实践:引入开发依赖的jar包
- [洛谷P1842] 奶牛玩杂技
- python田忌赛马
- bootstrap页面sidebar
- centos7下部署iptables环境纪录(关闭默认的firewalle)
- NumPy 字符串函数
- 基于jquery的ui选择之路