基环图 && 求联通块个数_cpp 构造图 求各联通块个数

          ------------------------------基环树------------------------------

前置知识

生成树：什么是生成树，生成树（生成森林）详解 (biancheng.net)​​​​​​ 

基环树：具有N个点N条边的连通图。

连通图必然存在生成树

基环树 

1.概念： 简单来说，基环树就是一个环上挂着一堆树。

2.两个性质（充要条件）

（1）连通图

（2）边数m=点数n

证明：

（1）必要性：一个基环树肯定是一个连通图（树是连通图，环是连通图）。我们断掉基环树环上的任意一条边，基环树就会成为一棵普通的树，树有m=n-1。

（2）充要性：由于性质（1）我们可知该图是一个连通图，连通图一定可以求一棵生成树，生成树有m=n-1，说明此时我们还有一条边没有用。因为这条没用的边无论加在生成树的任何地方，都只能构成一个环，所以该连通图一定是一基环树。

                                                                 （基环树）

应用：4216. 图中的环 - AcWing题库

思路：由性质判断该图是不是基环树，主要判断是不是一个连通图

1.并查集（连通块个数为1就是一个连通图）

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 1100;
 
int n, m, pre[N];
 
int find(int x)
{
    if(x == pre[x]) return pre[x];
    return pre[x] = find(pre[x]);
}
 
int main()
{
    cin >> n >> m;
    if(n != m)  puts("NO");
    else
    {
        for(int i &