首页 > 其他分享 >CF/505/D 题解

CF/505/D 题解

时间:2024-05-30 21:33:46浏览次数:28  
标签:连通 vis int 题解 CF ++ maxn low 505

思路


这道题的思路其实是根据样例图片来的。

首先第一张:

这张图片可以得知 $ n $ 个点没有环的时候最少需要 $ n - 1 $ 个点。

再看第二张:

这个图确实很难思考,但稍微思考一下如果我们把含有一个强连通分量的图变成一整个强连通图。

这个图的边数不就变成 $ n $ 了吗?

来推一下为什么这样最小:

因为强连通块需要的边数为 $ n $ 把他所在的图变成一个强连通图之后就是最小的了因为这个图中所有点都能互相到达了且只需要点的个数条边。

所以边数的数量就是含有强连通块的数量的图的点数之和,加上,没有含有强连通块的图的点数数量没有含有强连通块的图的数量。

因为每一个没有强连通分量需要点数个数 $ -1 $ 条边而含有强连通分量的图需要点数个数条边,因此我们可以得出最少需要的边数总点数的数量减去没有强连通分量图的数量。

这些问题解决了的话基本就好了,强连通块的数量就用 tarjan 求就行了。

AC 代码:

#include <bits/stdc++.h>
#include <map>
#include <bitset>
#define ll long long
#define prt printf
#define sc(ppt) scanf("%d" , &ppt)
using namespace std;
 
const int maxn = 1e5 + 1;
map<int , map<int , int>> G; // map来去重边 
int ans1 , ans2 , n , m , bj = 0; //题目需要 
int U[maxn] , V[maxn] , Cnt = 0 , cnt = 0 , H[maxn] , h[maxn]; //链式前向星 
int vis_d[maxn] ; // dfs
int sum , deep = 0 , top = 0 , dfn[maxn] , low[maxn] , vis[maxn] , stk[maxn] , color[maxn] , num[maxn]; // tarjan
struct edge{
	int next , to;
}e[maxn],e_d[maxn];
 
void add_edge(int u , int v){
	++cnt;
	e[cnt].next = h[u];
	e[cnt].to = v;
	h[u] = cnt;
} //tarjan 
 
void add(int u , int v){
	++Cnt;
	e_d[Cnt].next = H[u];
	e_d[Cnt].to = v;
	H[u] = Cnt;
} //缩点后 
 
void tarjan(int u){
	dfn[u] = ++deep , low[u] = deep , vis[u] = 1 , stk[++top] = u;
	for(int i=h[u] ; i ; i=e[i].next){
		int v = e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u] , low[v]);
		}
		else{
			if(vis[v]) low[u] = min(low[u] , dfn[v]);
		}
	}
	if(low[u] == dfn[u]){
		++sum;
		int v;
		do{
			v=stk[top--];
			vis[v] = false;
			color[v]=sum;
			num[sum]++;
		}while(u != v);
	}
} //板子 
 
void dfs(int u){
	vis_d[u] = 1;
	if(num[u] >= 2 && bj == 0){
		++ ans1;
		bj = 1;
	} //判断是否有强联通分量 
	for(int i=H[u] ; i ; i=e_d[i].next){
		int v = e_d[i].to;
		if(vis_d[v] != 1){
			dfs(v);
		}
	}
} //判断树 
 
signed main(){
	sc(n) ; sc(m) ;
	for(int i=1 ; i<=m ; i++){
		int u , v;
		sc(u) ; sc(v) ;
		U[i] = u;
		V[i] = v;
		add_edge(u , v);
	}
	for(int i=1 ; i<=n ; i++) if(!dfn[i]) tarjan(i);
	for(int i=1 ; i<=m ; i++){
		if(G[color[U[i]]][color[V[i]]] == 1 || color[U[i]] == color[V[i]]) continue;
		add(color[U[i]] , color[V[i]]);
		add(color[V[i]] , color[U[i]]);
		G[color[U[i]]][color[V[i]]] = 1;
	} //存双边变成树
	for(int i=1 ; i<=sum ; i++) {
		if(!vis_d[i]){
			bj = 0;
			++ans2, dfs(i);
		}
	} // 看有几棵树 
	prt("%d" , n - ans2 + ans1); // 数的数量 - 含有强连通树的数量就是没有强联通树的数量
	return 0;
}

标签:连通,vis,int,题解,CF,++,maxn,low,505
From: https://www.cnblogs.com/CaoSheng-blog/p/18223269

相关文章

  • P6342 [CCO2017] Vera 与道路建设 题解
    题目大意对于一个图w一共有v个点点的编号为1,2,...,v,对于点a与点b如果满足$a\tob$且$b\toa$使得每一条道路都只走过一次,那么我们称$a,b$为完美点对,当一个联通图只有$k$个完美点对时,称这个联通图为美丽公路网,要求求出一个美丽公路网......
  • Nikita and LCM题解
    题目大意给你一个数组$a$,令$t$为$a$的子序列且$t$中所有数的最小公倍数$\notina$求$t$数组中最多有多少个数。思路非常明显这是一道数学题,对于数组$a$我们首先从小到大拍一个序,然后我们可以求出$a$中所有数的最大公倍数,如果这个公倍数$\not=......
  • 「杂题乱刷」CF460C
    链接(luogu)链接(codeforces)有一个结论就是每次操作直接取一个存在目前最左边的最小值区间即可。但是我不会证啊......大家感性理解。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,ra......
  • CF1593D2. Half of Same
    题目链接:HalfofSame-洛谷|计算机科学教育新生态(luogu.com.cn)WA代码:#include<bits/stdc++.h>usingnamespacestd;#defineMAX44constintN=2e6+6;intarr[MAX];intcnt_1[N];//记录每个数出现的次数intcnt_2[N];//记录每个因数intmain(){intt;c......
  • CF2000
    CF1294FThreePathsonaTree除去整棵树是一条链的情况,答案的构成应该是两条链拼在一起。考虑贪心,先找到直径,再枚举不在直径上的点,求出它们到直径的距离最大值与直径加和即可。最后特判一下一条链的情况。CF1288EMessengerSimulator首先最靠上的位置很显然是\(1\)或者\(......
  • MITIT 2024 Spring Invitational Qualification 简要题解
    这个比赛没有找到题解,有点难绷,所以来写篇。(实际上是无聊时写的就是了)题面:https://codeforces.com/gym/105125/。目测难度是绿绿黄紫紫。A有点诈骗。其实策略是只保留\(\le3\)个数,然后就随便维护一下。\(O(n\logn)\)。Code#include<bits/stdc++.h>usingnamespaces......
  • Gym-100520A Andrew Stankevich Contest 45 A 题解
    AnalogousSetsGym-100520ASol1.集合生成函数将可重集合\(M\)映射为生成函数:\[F(M)=\sum_{m\inM}(\#m)\cdotx^m\]如果\(M\)的元素在\(\mathbbN\)上取值,那么,\(F(M)\)是多项式。2.\(\theta\)算子\[\theta(F)=x\cdotF'\]其中\(F'=\frac{dF}{dx}\)......
  • Springboot报class path resource [xxxxx.json] cannot be resolved to URL because i
    当Springboot解析resources文件下的json文件时,在本地环境好用,部署到服务器上找不到文件内容报错classpathresource[xxxxx.json]cannotberesolvedtoURLbecauseitdosenotexist问题排查(1)pom.xml文件配置<build><resources><resource><d......
  • 洛谷 P8725 [蓝桥杯 2020 省 AB3] 画中漂流 的题解
    题目大意传送门思路考虑使用时空复杂度为O(tm)O(tm)......
  • 洛谷 P8614 [蓝桥杯 2014 省 A] 波动数列 的题解
    题目大意求满足和为sss且ti=......