Compartir tecnología

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

[Fuente de la pregunta]
https://www.acwing.com/problema/contenido/3590/

[Descripción del Título]
Dado un gráfico no dirigido y todas sus aristas, determine si todos los vértices de este gráfico están conectados.

【Formato de entrada】
La entrada contiene varios conjuntos de datos.
La primera línea de cada conjunto de datos contiene dos números enteros n y m, que representan el número de puntos y aristas del gráfico no dirigido.
Las siguientes m líneas, cada línea contiene dos números enteros x, y, lo que indica que el punto x y el punto y están conectados.
Los puntos están numerados del 1 al n.
Puede haber en la imagen.doble filoyAuto-bucle。

[Formato de salida]
Cada conjunto de datos genera una línea y un resultado. Si todos los vértices están conectados, genera SÍ; de lo contrario, genera NO.

【rango de datos】
La entrada contiene hasta 10 conjuntos de datos.
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

【Muestra de entrada】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【Muestra de salida】
NO
SÍ

【Análisis de Algoritmos】
● El “Y busca en la colección."Para obtener detalles sobre la implementación del código, consulte:https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● El principio de usar dfs para determinar la gráfica conectada en esta pregunta radica en “dfs debe poder atravesar todos los puntos del gráfico conectado". Si un punto no se atraviesa, significa que no está conectado.

[Código de algoritmo: dfs + estrella delantera encadenada]
● plantilla de algoritmo dfs:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Para obtener detalles sobre las estrellas de avance de cadena, consulte: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
*/

[Código de algoritmo: dfs + matriz de adyacencia]
● plantilla de algoritmo dfs:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Implementación de matriz de adyacencia de gráfico no ponderado no dirigido: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
*/

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