AcWing 3587：连通图 ← dfs（邻接矩阵 or 链式前向星）

【题目来源】
https://www.acwing.com/problem/content/3590/

【题目描述】
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

【输入格式】
输入包含若干组数据。
每组数据第一行包含两个整数 n 和 m，表示无向图的点和边数。
接下来 m 行，每行包含两个整数 x,y，表示点 x 和点 y 相连。
点的编号从 1 到 n。
图中可能存在重边和自环。

【输出格式】
每组数据输出一行，一个结果，如果所有顶点都是连通的，输出 YES，否则输出 NO。

【数据范围】
输入最多包含 10 组数据。
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

【输入样例】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【输出样例】
NO
YES

【算法分析】
● 本题的“并查集”代码实现详见：https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● 本题利用 dfs 判断连通图的原理在于“dfs必然能够遍历到连通图的所有点”。如果有点没有被遍历到，说明不连通。

【算法代码：dfs+链式前向星】
● dfs算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 链式前向星详见：https://blog.csdn.net/hnjzsyjyj/article/details/139369904

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+5;
const int M=5e3+5;
int e[M<<1],ne[M<<1],h[N],idx;
bool st[N];
int n,m;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u) {
    st[u]=1;
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}

int main() {
    while(cin>>n>>m) {
        memset(st,false,sizeof st);
        memset(h,-1,sizeof h);
        idx=0;
        while(m--) {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }

        dfs(1);

        bool flag=true;
        for(int i=1; i<=n; i++)
            if(!st[i]) {
                flag=false;
                break;
            }

        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}


/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3

out:
NO
YES
*/

【算法代码：dfs+邻接矩阵】
● dfs算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 无向无权图的邻接矩阵实现：https://blog.csdn.net/hnjzsyjyj/article/details/116245897

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
int g[N][N];
bool st[N];
int n,m;

void dfs(int u) {
    st[u]=true;
    for(int i=1; i<=n; i++)
        if(!st[i] && g[u][i]!=0) dfs(i);
}

int main() {
    while(cin>>n>>m) {
        memset(g,0,sizeof g);
        memset(st,false,sizeof st);
        int x,y;
        while(m--) {
            cin>>x>>y;
            g[x][y]=g[y][x]=1;
        }
        dfs(1);
        int i;
        for(i=1; i<=n; i++) {
            if(!st[i]) break;
        }
        if(i<=n) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3

out:
NO
YES
*/

【参考文献】
https://www.acwing.com/solution/content/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/118736059
https://blog.csdn.net/hnjzsyjyj/article/details/139369904