Question

Pesquise a implementação ou Implemente a busca de pontes em grafos.


(SEM BRINCADEIRAS, POR FAVOR NAO RESPONDER QUALQUER COISA SÓ PELOS PONTOS, OU ESTAREI DENUNCIANDO)

Desde ja agradeço a todos que tentar.

Answer 1

Resposta:

Pelo que entendi tu vai ter q fazer uma matriz pra indicar onde existe ligação entre os pontos

Como não é um grafo direcionado ( digrafo no caso)  tu tem por exemplo

ligação de 1 para 2 , como tu tem ligação de 2 para 1

desse modo tu pode criar uma matriz  (nesse caso 6x6)

onde tem ligação entre a linha e a coluna tu marca com 1

onde não tem tu marca com 0

          1    2   3   4   5   6

1         0    1    1    1    0    0

2        1     0   1    0   0    0

3        1     1    0    0   1     1

4        1    0    0    0   0    0

5        0    0    1    0    0   1

6        0    0    1    0    1    0

int n; // número de nós

vector<vector<int>> adj; // lista de adjacência - grafo

vector<bool> visited;

vector<int> tin, low;

int timer;

void dfs(int v, int p = -1) {

   visited[v] = true;

   tin[v] = low[v] = timer++;

   for (int to : adj[v]) {

       if (to == p) continue;

       if (visited[to]) {

           low[v] = min(low[v], tin[to]);

       } else {

           dfs(to, v);

           low[v] = min(low[v], low[to]);

           if (low[to] > tin[v])

               IS_BRIDGE(v, to);

       }

   }

}

void find_bridges() {

   timer = 0;

   visited.assign(n, false);

   tin.assign(n, -1);

   low.assign(n, -1);

   for (int i = 0; i < n; ++i) {

       if (!visited[i])

           dfs(i);

   }

}

Explicação: