本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14077 [GESP202509 七级] 连通图 - 洛谷【题目描述】给定一张包含n nn个结点与m mm条边的无向图结点依次以1 , 2 , … , n 1,2,…,n1,2,…,n编号第i ii条边1 ≤ i ≤ m 1≤i≤m1≤i≤m连接结点u i u_iui​与结点v i v_ivi​。如果从一个结点经过若干条边可以到达另一个结点则称这两个结点是连通的。你需要向图中加入若干条边使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。注意给出的图中可能包含重边与自环。【输入】第一行两个正整数n , m n,mn,m表示图的点数与边数。接下来m mm行每行两个正整数u i , v i u_i,v_iui​,vi​表示图中一条连接结点u i u_iui​与结点v i v_ivi​的边。【输出】输出一行一个整数表示使得图中任意两个结点连通所需加入的边的最少数量。【输入样例】4 4 1 2 2 3 3 1 1 4【输出样例】0【算法标签】#普及-# #并查集#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义最大节点数intn;// 节点数量intm;// 边数量intans0;// 存储连通分量数量intp[N];// 并查集父节点数组boolvis[N];// 标记数组记录是否已统计过该连通分量/** * 并查集查找函数带路径压缩 * param x 要查找的节点 * return 节点x的根节点 */intfind(intx){if(p[x]!x)// 如果当前节点不是根节点{p[x]find(p[x]);// 路径压缩}returnp[x];}intmain(){// 输入节点数和边数cinnm;// 初始化并查集每个节点的父节点指向自己for(inti1;in;i){p[i]i;}// 处理每条边合并连通分量while(m--){inta,b;cinab;// 合并a和b所在的连通分量p[find(a)]find(b);}// 统计连通分量数量for(inti1;in;i){intxfind(i);// 找到节点i的根节点if(!vis[x])// 如果该连通分量未被统计过{ans;// 连通分量数量加1vis[x]1;// 标记该连通分量已统计}}/** * 输出结果 * 连通分量数量减1即需要添加的边数 * 因为要将所有连通分量连接成一棵树需要ans-1条边 */coutans-1endl;return0;}【运行结果】4 4 1 2 2 3 3 1 1 4 0