【简单图论】CF1833 E

￡神魔★判官ぃ 2024-03-22 19:53 44阅读 0赞

[Problem - E - Codeforces][]

题意：

![e5307033af4e492996bee444f2c9fecf.png][]

![0ee52ece74894ab582fbfce7c98e58fd.png][] ![7c269eb2367f4d86ae5fa725619ee7d8.png][]

思路：

显然，最大值就是什么边都不连的连通块个数，最小值就是能连的都连上

那就是，如果一个连通块存在度为1的点，就把它当作接口连接

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std; 
    
    const int mxn=2e5+10;
    
    int N,x;
    int F[mxn],FG[mxn],sz[mxn];
    
    set<int> G[mxn];
    
    int find(int x){
    	return F[x]=(x==F[x])?x:find(F[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2){
    		F[f1]=f2;
    		sz[f2]+=sz[f1];
    	}
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		F[i]=i;
    		sz[i]=1;
    		G[i].clear();
    		FG[i]=0;
    	}
    	for(int i=1;i<=N;i++){
    		cin>>x;
    		G[i].insert(x);
    		G[x].insert(i);
    		join(x,i);
    	}
    	for(int i=1;i<=N;i++){
    		FG[find(i)]|=(G[i].size()==1);
    	}
    	int cnt=0,res=0;
    	for(int i=1;i<=N;i++){
    		if(find(i)==i){
    			res++;
    			cnt+=FG[i];
    		}
    	}
    	cout<<min(res,res-cnt+1)<<" "<<res<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1833/problem/E
[e5307033af4e492996bee444f2c9fecf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5362a0d4b81f4c90a1cff5c0c5df51f8.png
[0ee52ece74894ab582fbfce7c98e58fd.png]: https://img-blog.csdnimg.cn/0ee52ece74894ab582fbfce7c98e58fd.png
[7c269eb2367f4d86ae5fa725619ee7d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/254d6d9d48f94310b66f6aa3a8ca1045.png

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关【*1900 图论+枚举思想】CF1328 E

[Problem - E - Codeforces][] 题意： ![5f242b3e379b424cb713c6418d07f247.png][] ![5e58cd37

约定不等于承诺〃/ 2024年03月22日 21:14/ 0 赞/ 50 阅读

相关【简单图论】CF1833 E

[Problem - E - Codeforces][] 题意： ![e5307033af4e492996bee444f2c9fecf.png][] ![0ee52ece

￡神魔★判官ぃ/ 2024年03月22日 19:53/ 0 赞/ 45 阅读

相关【枚举】CF1833 D

[Problem - D - Codeforces][] 题意：给定一个序列，让你找一个区间，翻转区间内的数，交换前缀和后缀，让结果数组的字典序最大 ![c14db1d

深碍√TFBOYSˉ_/ 2024年03月22日 19:49/ 0 赞/ 55 阅读

相关【算组合数】CF1833 F

少见地秒了这道1700，要是以后都这样就好了.... [Problem - F - Codeforces][] 题意：给定一个数列，让你在这个数列里找一个大小为M的子

灰太狼/ 2024年03月22日 19:48/ 0 赞/ 12 阅读

相关【树上操作】定长裁剪 CF1833 G

[Problem - G - Codeforces][] 题意：给定一棵n个节点的树，请你减掉一些边，使得剪掉后的每个树只有三个节点，如果可以，第一行返回减掉边的数

今天药忘吃喽~/ 2024年03月18日 00:38/ 0 赞/ 44 阅读

相关【简单图论】CF898 div4 H

[Problem - H - Codeforces][] 题意： ![4b37a99e5b464ba681c364f7b47a7a52.png][] 思路：手玩一下样

爱被打了一巴掌/ 2024年03月01日 01:46/ 0 赞/ 62 阅读

相关 CF1037E图论思维（set::erase的用法）

[传送门][Link 1] include<bits/stdc++.h> using namespace std; define fir first

╰+哭是因爲堅強的太久メ/ 2022年05月14日 07:27/ 0 赞/ 65 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 187 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 185 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 235 阅读