URI (BEECROWD) - 3171 - Cordão de Led - Estruturas e Bibliotecas - C e C++

Olá! Hoje vou apresentar a solução de mais um problema da categoria estruturas e bibliotecas! As coisas estão corridas por aqui, então só agora consegui um tempinho para trazer novas soluções. Acompanhe na sequência do post!

Plataforma: URI (BEECROWD)

Problema: 3171

Enunciado: Mariazinha quer montar sua árvore de Natal com os cordões de led comprados no ano passado. O problema é que sua irmã caçula acabou cortando estes cordões em vários pedaços. 

Mariazinha quer saber se após unir estes pedaços (enumerados com uma etiqueta por ela de 1 até N) o cordão está totalmente unido ou não, pois se faltar unir algum dos segmentos, as luzes do cordão de led não irão funcionar.

Escreva um programa que, dada uma série de ligações entre segmentos de cordões de led, indique se o cordão estará Completo ou Incompleto.

Solução:

Este é um problema que se resolve com um algoritmo clássico de grafos conhecido como BFS (Breadth-First Search), ou busca em largura.

Código em C++:

Utilizei a estrutura vector para criar um vetor de vetores de inteiros, simulando uma matriz de adjacência. Usei vector porque em C++ é mais fácil e tudo já está pronto para uso em bits/stdc++.h.

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;

bool bfs(int inicio, int n) {
   vector<bool> visitado(adj.size(), false);
   vector<int> q;
   q.push_back(inicio);
   int resposta = 0;
   visitado[inicio] = true;
   int vis;
   while (!q.empty()) {
      vis = q[0];
      resposta++;
      q.erase(q.begin());
      for (int i = 0; i < adj[vis].size(); i++) {
         if (adj[vis][i] == 1 && (!visitado[i])) {
            q.push_back(i);
            visitado[i] = true;
	 }
      }
   }
   return resposta == n;
}

int main() {
   int n, l, x, y;
   cin >> n >> l;
   adj = vector<vector<int>>(n, vector<int>(n, 0));
   while (l--) {
      cin >> x >> y;
      int indiceX = x - 1;
      int indiceY = y - 1;
      adj[indiceX][indiceY] = 1;
      adj[indiceY][indiceX] = 1;
   }
   if (!bfs(0, n))
      cout << "IN";
   cout << "COMPLETO" << endl;
   return 0;
}

Código em C:

Aqui criei uma matriz global de adjacência apenas para facilitar a sua manipulação.

#include <stdio.h>
#include <string.h>

#define MAX_TAM 100

int adj[MAX_TAM][MAX_TAM];
int visitado[MAX_TAM];

int bfs(int inicio, int n) {
    for (int i = 0; i < n; i++) {
        visitado[i] = 0;
    }

    int fila[MAX_TAM];
    int primeiro = 0;
    int ultimo = 0;
    int resposta = 0;

    visitado[inicio] = 1;
    fila[ultimo++] = inicio;

    while (primeiro < ultimo) {
        int atual = fila[primeiro++];
        resposta++;

        for (int i = 0; i < n; i++) {
            if (adj[atual][i] == 1 && !visitado[i]) {
                fila[ultimo++] = i;
                visitado[i] = 1;
            }
        }
    }

    return resposta == n;

}

int main() {
    int n, l, x, y;
    scanf("%d %d", &n, &l);
    memset(adj, 0, n * sizeof(int));

    while (l--) {
        scanf("%d %d", &x, &y);
        int indiceX = x - 1;
        int indiceY = y - 1;
        adj[indiceX][indiceY] = 1;
        adj[indiceY][indiceX] = 1;
    }

    if (!bfs(0, n))
        printf("IN");

    printf("COMPLETO\n");

    return 0;
}

Espero que tenham gostado de mais esse post! O PIX para doações segue sendo a chave aleatória 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Ajude-nos para que as postagens sigam acontecendo!