Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

【Source of the topic】
https://www.acwing.com/problem/content/3590/

【Topic Description】
Given an undirected graph and all its edges, determine whether all vertices of the graph are connected.

【Input format】
The input contains several sets of data.
The first line of each data set contains two integers n and m, representing the number of vertices and edges in the undirected graph.
The next m lines each contain two integers x and y, indicating that point x is connected to point y.
The points are numbered from 1 to n.
The picture may existHeavy EdgeandSelf-loop。

Output format
Output one line and one result for each set of data. If all vertices are connected, output YES, otherwise output NO.

【data range】
The input contains at most 10 sets of data.
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

[Input example]
4 3
1 2
2 3
3 2
3 2
1 2
2 3

Output sample
NO
YES

【Analysis of Algorithms】
● The “Union Search"For code implementation, see:https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● The principle of using dfs to determine the connected graph in this question is "DFS must be able to traverse all points in the connected graphIf a point is not traversed, it means it is not connected.

[Algorithm code: dfs+chain forward star]
● dfs algorithm template:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Chain forward star details: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
*/

[Algorithm code: dfs+adjacency matrix]
● dfs algorithm template:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Adjacency matrix implementation of undirected unweighted graph: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
*/

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