Partage de technologie

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

[Source de la question]
https://www.acwing.com/problem/content/3590/

[Description du titre]
Étant donné un graphe non orienté et toutes ses arêtes, déterminez si tous les sommets de ce graphe sont connectés.

【Format d'entrée】
L'entrée contient plusieurs ensembles de données.
La première ligne de chaque ensemble de données contient deux entiers n et m, représentant le nombre de points et d'arêtes du graphe non orienté.
Les m lignes suivantes, chaque ligne contient deux entiers x, y, indiquant que le point x et le point y sont connectés.
Les points sont numérotés de 1 à n.
Il y en a peut-être sur la photodouble tranchantetAuto-boucle。

[Format de sortie]
Chaque ensemble de données génère une ligne et un résultat. Si tous les sommets sont connectés, affichez OUI, sinon affichez NON.

【plage de données】
L'entrée contient jusqu'à 10 ensembles de données.
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

【Échantillon d'entrée】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【Échantillon de sortie】
NON
OUI

【Analyse des algorithmes】
● Le « Et fouillez la collection"Pour plus de détails sur l'implémentation du code, veuillez consulter :https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● Le principe de l'utilisation de dfs pour déterminer le graphe connecté dans cette question réside dans «dfs doit être capable de parcourir tous les points du graphe connecté". Si un point n'est pas parcouru, cela signifie qu'il n'est pas connecté.

[Code de l'algorithme : dfs + étoile avant enchaînée]
● modèle d'algorithme dfs :https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Pour plus de détails sur les étoiles en chaîne, veuillez consulter :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
*/

[Code de l'algorithme : dfs+matrice de contiguïté]
● modèle d'algorithme dfs :https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Implémentation de la matrice de contiguïté d'un graphe non orienté non pondéré :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
*/

【les références】
https://www.acwing.com/solution/content/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/118736059
https://blog.csdn.net/hnjzsyjyj/article/details/139369904