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 */
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)
Pergunta
Igor Terriaga
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
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.