Ir para conteúdo
Fórum Script Brasil
  • 0

Implementação de um algoritmo com UNION-FIND


Igor Terriaga

Pergunta

Pessoal, to tentando resolver uma questão aqui, fiz algumas coisas mas ainda preciso de ajuda...

Segue a questão e o código:

Numa cidade há n pessoas. Sabe-se que existe m pares de pessoas que são
amigos na cidade. Sabendo que se A ´e amigo de B e B ´e amigo de C, então
A é amigo de C. Qual o tamanho do maior grupo de amigos quando: n = 10,
m = 12, e os pares são = (1,2), (3,1), (3,4), (5,4), (3,5), (4,6), (5,2), (2,1),
(7,10), (1,2), (9,10), (8,9)? (Dica: resolve-se usando conjuntos union-find).

Código ->>

#include <stdio.h>
#include <stdlib.h>
/* Você possui N nós, inicialmente desconectados.
Serão adicionadas M arestas, e após cada operação, deseja-se saber quais vértices pertencem a qual componente conexa do grafo.
Mais especificamente, as seguintes operações podem ser realizadas:
Union(A, B): adicionar uma aresta entre A e B.
Find(A): dizer em qual componente conexa está o vértice A.
inicialmente temos parent[x] = x e rank[x] = 0 */

int find(int x,int []parent) {

    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void union(int a, int b, int []rank ) {
    int rank [];
    int x = find(a), y = find(b);
    if (x==y) return;
    if (rank[x] < rank[y]) {
        parent[x] = y;
    }
    else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
int main()
{
    int n = 10, m=12;
    int parent [];
    int rank [];
    union (1,2);
    union (3,1);
    union (3,4);
    union (5,4);
    union (3,5);
    union (4,6);
    union (5,2);
    union (2,1);
    union (7,10);
    union (1,2);
    union (9,10);
    union (8,9)


    return 0;
}
 

Link para o comentário
Compartilhar em outros sites

0 respostass a esta questão

Posts Recomendados

Até agora não há respostas para essa pergunta

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152,3k
    • Posts
      652,3k
×
×
  • Criar Novo...