一、解题思路

• （1）判断所有顶点连通？
• （2）什么是所有顶点连通？ 答：所有顶点都有路径相连
• （3）怎么保证有路径相连？ 答：看是否属于同一个集合
• （4）如何判断是一个集合？ 答：集合逻辑上表示为树结构，对于每一个元素不断向上找根节点，如果根节点相同则连个元素是一个集合
• 综上所述：判断所有顶点连通 => 判断集合个数 =>个数为1，则为连通
• 补充：（我的理解）连通分量其实就是一个图里面并查集集合数量的多少

二、解题流程

1. 循环输入n：图顶点数、m：图边数
2. 初始化：

• 初始化2个数组 father，height（Initial函数）
• 将所有顶点看为一个独立的个体，此时爸爸是自己，高度为0

3. 输入相连的顶点：

• （1）查找顶点所在集合即“查找集合根节点”（Find函数）
• （2）不在同一集合进行合并（Union函数）

4. 计算集合个数：

• （1）初始化answer为0
• （2）如果全部连通，则集合个数为1，只有根节点的父亲为自己，answer++为1，连通，输出 YES
• （3）如果是两个集合，有两个根节点的父亲为自己，answer++操作两次，answer=2，不连通，输出 NO。以此类推

三、代码如下（C++）

#include<iostream>
using namespace std;

const int MAXN=1000+10;
int father[MAXN];
int height[MAXN];

//初始化，每个顶点是一个独立的个体，爸爸是自己，高度为0
void Initial(int n)   
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        height[i]=0;
    }
    return ;
}

//找根节点，不断的Find（father【i】）
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}

//合并
void Union(int x,int y)
{
    x=Find(x);  // 找到x的根节点
    y=Find(y);  // 找到y的根节点
    if(x!=y)    // 两个不是一个集合
    {
        if(height[x]<height[y])
            father[x]=y;
        else if(height[x]>height[y])
            father[y]=x;
        else
        {
            father[x]=y;
            height[y]++;
        }
    }
    return ;
}

int main()
{
    int n,m;  // n：图顶点数 m：图边数目
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        
        Initial(n); 
        while(m--)
        {
            int x,y;
            scanf("%d",&x);
            scanf("%d",&y);
            Union(x, y);
        }
        int answer=0;
        for(int i=1;i<=n;i++)
        {
            if(Find(i)==i)
                answer++;
        }
        if(answer!=1)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}