Lenguaje C, programación de árboles de juicio.

Generalmente, el algoritmo de árbol de expansión mínima se utiliza para preguntas de construcción de árboles, pero en vista de la particularidad de su pregunta, puede buscarlo directamente y se puede pasar la complejidad temporal de O(n)

#include

#include

usando el espacio de nombres std;

bool bo[1100];

int n,m,a[1100][1100];

búsqueda vacía(int x){

for(int i=1;i<=a[ x][0 ];i++){//Preguntar si cada punto conectado a x está teñido

int y=a[x][i];

if(!bo[ y ]){//Si y no está teñido, tiñe y y usa y para actualizar otros nodos

bo[y]=1;

search(y);

}

}

}

int main(){

scanf("%d%d",&n ,&m);//Aquí debe ingresar el número de nodos y aristas. Por ejemplo, para su conjunto de datos, ingrese 10 9 para representar 10 puntos y 9 aristas

if(m

por (int i=1;i<=m;i++){

int x,y;scanf("%d%d",&x,&y);

a[x ][++a[x][0]]=y;//Registra que el punto x se puede conectar al punto y, lo mismo a continuación

a[y][++a[y ][ 0]]=x;

}

memset(bo,0,sizeof(bo));// Al principio, no hay ningún nodo excepto el nodo 1 en este gráfico , y luego comienza a colorear del 1 a otros puntos

bo[1]=1;

search(1);

for(int i=1 ; i<=n;i++)

if(!bo[i]){//Si el punto no está teñido, significa que no se puede conectar a un árbol

printf( "NO\ n");

devuelve 0;

}

printf("SÍ\n");

devuelve 0 ;

}