题目描述给你一个整数n。现有一个包含n个顶点的无向图顶点按从0到n - 1编号。给你一个二维整数数组edges其中edges[i] [ai, bi]表示顶点ai和bi之间存在一条无向边。返回图中完全连通分量的数量。相关定义连通分量如果在子图中任意两个顶点之间都存在路径并且子图中没有任何一个顶点与子图外部的顶点共享边则称其为连通分量。完全连通分量如果连通分量中每对节点之间都存在一条边则称其为完全连通分量。示例 1输入n 6, edges [[0,1],[0,2],[1,2],[3,4]]输出3解释如图所示可以看到此图所有分量都是完全连通分量。示例 2输入n 6, edges [[0,1],[0,2],[1,2],[3,4],[3,5]]输出1解释包含节点 0、1 和 2 的分量是完全连通分量因为每对节点之间都存在一条边。包含节点 3、4 和 5 的分量不是完全连通分量因为节点 4 和 5 之间不存在边。因此图中完全连接分量的数量是 1。提示1 n 500 edges.length n * (n - 1) / 2edges[i].length 20 ai, bi n - 1ai ! bi不存在重复的边AC 代码经过前天每日一题 针对图的路径存在性查询Ⅰ并查集的严肃学习今天的题目思路很清晰地写出来了classSolution{public:intfindFather(vectorintgroup,intn){if(group[n]0)returnn;returngroup[n]findFather(group,group[n]);}// 将b所在的连通分量合并到a中vectorintUnion(vectorintgroup,inta,intb){intfather_afindFather(group,a);intfather_bfindFather(group,b);group[father_a]group[father_b];group[father_b]father_a;returngroup;}intcountCompleteComponents(intn,vectorvectorintedges){// ideal 存储所有完全连通分量中边的数量// 如 ideal[2]1 意为有 2 个节点的完全连通分量应该有 1 条边vectorintideal;//ideal.emplace_back(0);inttem0;// n 最大为 50所以想到了可以直接设定好for(inti0;i51;i){ideal.emplace_back(tem);temi;}vectorintgroup(n,-1);for(autoedge:edges){intfather_0findFather(group,edge[0]);intfather_1findFather(group,edge[1]);if(father_0father_1)continue;if(group[father_0]group[father_1])swap(edge[0],edge[1]);groupUnion(group,father_0,father_1);}setintFathers;// 存储所有连通分量的根节点for(inti0;in;i){Fathers.insert(findFather(group,i));}// 该哈希表记录每个连通分量的实际的边的数量// edgeNumber[0]1 意为以 0 为根节点的连通分量有 1 条边unordered_mapint,intedgeNumber;for(autox:Fathers)edgeNumber.emplace(x,0);for(autoedge:edges)edgeNumber[findFather(group,edge[0])];intres0;for(auto[key,value]:edgeNumber){if(ideal[-group[key]]value)res;}returnres;}};学习笔记C 常用容器操作速查表vector、set、unordered_map操作vectorsetunordered_map插入v.push_back(x)s.insert(x)umap[key] value访问v[i]不支持umap.at(key)查找std::find(v.begin(), v.end(), x)s.find(x)umap.find(key)删除v.pop_back()尾部v.erase(it)指定位置s.erase(x)umap.erase(key)遍历for (auto x : v)for (auto x : s)for (auto [k, v] : umap)C17for (auto p : umap)C11大小v.size()s.size()umap.size()判空v.empty()s.empty()umap.empty()清空v.clear()s.clear()umap.clear()