【简单图论】CF1833 E

￡神魔★判官ぃ 2024-03-22 19:53 79阅读 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 条评论，79人围观）

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

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 71 阅读

相关【简单图论】CF1833 E

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

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

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

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

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

相关【简单图论】CF898 div4 H

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

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

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 11 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 117 阅读

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

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

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

相关 [CF1111E]Tree

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

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

相关 CF 166E Tetrahedron

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

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

相关 cf 1009E

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

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