Dado un gráfico con N Nodes y sus valores definidos en la array A, la tarea es encontrar el tamaño de componente más grande en un gráfico conectando Nodes no coprimos. Una arista se encuentra entre dos Nodes U y V si no son coprimos, lo que significa que el máximo común divisor de A[U] y A[V] debe ser mayor que 1.
Ejemplos:
Input : A = [4, 6, 15, 35]
Output : 4
Graph will be :
4
|
6
|
15
|
35
Input : A = [2, 3, 6, 7, 4, 12, 21, 39]
Output : 8
Enfoque ingenuo:
podemos iterar sobre todos los pares de Nodes y verificar si son coprimos o no. Si no son coprimos, los conectaremos. Una vez que se crea el gráfico, aplicaremos la primera búsqueda en profundidad para encontrar el tamaño máximo del componente.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int dfs(int u, vector<int>* adj, int vis[])
{
// mark this node as visited
vis[u] = 1;
int componentSize = 1;
// apply dfs and add nodes belonging to this component
for (auto it : adj[u]) {
if (!vis[it]) {
componentSize += dfs(it, adj, vis);
}
}
return componentSize;
}
int maximumComponentSize(int a[], int n)
{
// create graph and store in adjacency list form
vector<int> adj[n];
// iterate over all pair of nodes
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// if not co-prime
if (__gcd(a[i], a[j]) > 1)
// build undirected graph
adj[i].push_back(j);
adj[j].push_back(i);
}
}
int answer = 0;
// visited array for dfs
int vis[n];
for(int k=0;k<n;k++){
vis[k]=0;
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
answer = max(answer, dfs(i, adj, vis));
}
}
return answer;
}
// Driver Code
int main()
{
int n = 8;
int A[] = { 2, 3, 6, 7, 4, 12, 21, 39 };
cout << maximumComponentSize(A, n);
return 0;
}
Java
import java.util.*;
class GFG{
static int dfs(int u, Vector<Integer> []adj,
int vis[])
{
// Mark this node as visited
vis[u] = 1;
int componentSize = 1;
// Apply dfs and add nodes belonging
// to this component
for(int it : adj[u])
{
if (vis[it] == 0)
{
componentSize += dfs(it, adj, vis);
}
}
return componentSize;
}
static int maximumComponentSize(int a[], int n)
{
// Create graph and store in adjacency
// list form
@SuppressWarnings("unchecked")
Vector<Integer> []adj = new Vector[n];
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// Iterate over all pair of nodes
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If not co-prime
if (__gcd(a[i], a[j]) > 1)
// Build undirected graph
adj[i].add(j);
adj[j].add(i);
}
}
int answer = 0;
// Visited array for dfs
int []vis = new int[n];
for(int k = 0; k < n; k++)
{
vis[k] = 0;
}
for(int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
answer = Math.max(answer,
dfs(i, adj, vis));
}
}
return answer;
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver Code
public static void main(String[] args)
{
int n = 8;
int A[] = { 2, 3, 6, 7, 4, 12, 21, 39 };
System.out.print(maximumComponentSize(A, n));
}
}
// This code is contributed by Amit Katiyar
Python3
from math import gcd def dfs(u, adj, vis): # mark this node as visited vis[u] = 1 componentSize = 1 # apply dfs and add nodes belonging to this component for x in adj[u]: if (vis[x] == 0): componentSize += dfs(x, adj, vis) return componentSize def maximumComponentSize(a,n): # create graph and store in adjacency list form adj = [[] for i in range(n)] # iterate over all pair of nodes for i in range(n): for j in range(i + 1, n): # if not co-prime if (gcd(a[i], a[j]) > 1): # build undirected graph adj[i].append(j) adj[j].append(i) answer = 0 # visited array for dfs vis = [0 for i in range(n)] for i in range(n): if (vis[i]==False): answer = max(answer, dfs(i, adj, vis)) return answer # Driver Code if __name__ == '__main__': n = 8 A = [2, 3, 6, 7, 4, 12, 21, 39] print(maximumComponentSize(A, n)) # This code is contributed by Bhupendra_Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static int dfs(int u,
List<int> []adj,
int []vis)
{
// Mark this node as visited
vis[u] = 1;
int componentSize = 1;
// Apply dfs and add nodes belonging
// to this component
foreach(int it in adj[u])
{
if (vis[it] == 0)
{
componentSize += dfs(it,
adj, vis);
}
}
return componentSize;
}
static int maximumComponentSize(int []a,
int n)
{
// Create graph and store in adjacency
// list form
List<int> []adj = new List<int>[n];
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// Iterate over all pair of nodes
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If not co-prime
if (__gcd(a[i], a[j]) > 1)
// Build undirected graph
adj[i].Add(j);
adj[j].Add(i);
}
}
int answer = 0;
// Visited array for dfs
int []vis = new int[n];
for(int k = 0; k < n; k++)
{
vis[k] = 0;
}
for(int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
answer = Math.Max(answer,
dfs(i,
adj, vis));
}
}
return answer;
}
static int __gcd(int a, int b)
{
return b == 0 ? a :
__gcd(b, a % b);
}
// Driver Code
public static void Main(String[] args)
{
int n = 8;
int []A = {2, 3, 6, 7,
4, 12, 21, 39};
Console.Write(maximumComponentSize(A, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
function dfs(u, adj, vis)
{
// Mark this node as visited
vis[u] = 1;
let componentSize = 1;
// Apply dfs and add nodes belonging
// to this component
for(let it in adj[u])
{
if (vis[it] == 0)
{
componentSize += dfs(it,
adj, vis);
}
}
return componentSize;
}
function maximumComponentSize(a, n)
{
// Create graph and store in adjacency
// list form
let adj = new Array(n);
for (var i = 0; i < adj.length; i++) {
adj[i] = new Array(2);
}
for (var i = 0; i < adj.length; i++) {
for (var j = 0; j < adj.length; j++) {
adj[i][j] = 0;
}
}
// Iterate over all pair of nodes
for(let i = 0; i < n; i++)
{
for(let j = i + 1; j < n; j++)
{
// If not co-prime
if (__gcd(a[i], a[j]) > 1)
// Build undirected graph
adj[i].push(j);
adj[j].push(i);
}
}
let answer = 0;
// Visited array for dfs
let vis = Array.from({length: n}, (_, i) => 0);
for(let k = 0; k < n; k++)
{
vis[k] = 0;
}
for(let i = 0; i < n; i++)
{
if (vis[i] == 0)
{
answer = Math.max(answer,
dfs(i,
adj, vis));
}
}
return answer;
}
function __gcd(a, b)
{
return b == 0 ? a :
__gcd(b, a % b);
}
// Driver Code
let n = 8;
let A = [2, 3, 6, 7, 4, 12, 21, 39];
document.write(maximumComponentSize(A, n));
</script>
Producción:
8
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente
- Para que dos números cualesquiera no sean coprimos, deben tener al menos un factor común. Entonces, en lugar de atravesar todos los pares, es mejor factorizar en factores primos cada valor de Node. La idea es juntar números con factores comunes como un solo grupo.
- La descomposición en factores primos se puede hacer de manera eficiente utilizando la criba de Eratóstenes . Para agrupar Nodes, utilizaremos una estructura de datos de conjuntos disjuntos (unión por rango y compresión de ruta) .
- Se almacenará la siguiente información:
par[i] -> representa el padre del Node i
size[i] -> representa el tamaño del Node componente al que pertenece
id[p] -> representa qué número primo del Node p se vio por primera vez como un factor de A[i ]
- Para cada valor de Node, factorizaremos y almacenaremos los factores primos en el conjunto S. Iterará cada elemento de S. Si el número primo se ve por primera vez como un factor de algún número (id[p] es cero), entonces marque esta identificación principal con el índice actual. Si se ha marcado este primo, simplemente fusione este Node con el de id[p].
De esta forma, todos los Nodes pertenecerán finalmente a algún componente, y size[i] será el tamaño del Node del componente al que pertenezco.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// smallest prime factor
int spf[100005];
// Sieve of Eratosthenes
void sieve()
{
for (int i = 2; i < 100005; i++) {
// is spf[i] = 0, then it's prime
if (spf[i] == 0) {
spf[i] = i;
for (int j = 2 * i; j < 100005; j += i) {
// smallest prime factor of all multiples is i
if (spf[j] == 0)
spf[j] = i;
}
}
}
}
// Prime factorise n,
// and store prime factors in set s
void factorize(int n, set<int>& s)
{
while (n > 1) {
int z = spf[n];
s.insert(z);
while (n % z == 0)
n /= z;
}
}
// for implementing DSU
int id[100005];
int par[100005];
int sizeContainer[100005];
// root of component of node i
int root(int i)
{
if (par[i] == i)
return i;
// finding root as well as applying
// path compression
else
return par[i] = root(par[i]);
}
// merging two components
void merge(int a, int b)
{
// find roots of both components
int p = root(a);
int q = root(b);
// if already belonging to the same component
if (p == q)
return;
// Union by rank, the rank in this case is
// sizeContainer of the component.
// Smaller sizeContainer will be merged into
// larger, so the larger's root will be
// final root
if (sizeContainer[p] > sizeContainer[q])
swap(p, q);
par[p] = q;
sizeContainer[q] += sizeContainer[p];
}
// Function to find the maximum sized container
int maximumComponentsizeContainer(int a[], int n)
{
// intitalise the parents,
// and component sizeContainer
for (int i = 0; i < 100005; i++) {
// initially all component sizeContainers are 1
// ans each node it parent of itself
par[i] = i;
sizeContainer[i] = 1;
}
sieve();
for (int i = 0; i < n; i++) {
// store prime factors of a[i] in s
set<int> s;
factorize(a[i], s);
for (auto it : s) {
// if this prime is seen as a factor
// for the first time
if (id[it] == 0)
id[it] = i + 1;
// if not then merge with that component
// in which this prime was previously seen
else
merge(i + 1, id[it]);
}
}
int answer = 0;
// maximum of sizeContainer of all components
for (int i = 0; i < n; i++)
answer = max(answer, sizeContainer[i]);
return answer;
}
// Driver Code
int main()
{
int n = 8;
int A[] = { 2, 3, 6, 7, 4, 12, 21, 39 };
cout << maximumComponentsizeContainer(A, n);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// smallest prime factor
static int []spf = new int[100005];
// Sieve of Eratosthenes
static void sieve()
{
for (int i = 2; i < 100005; i++)
{
// is spf[i] = 0, then it's prime
if (spf[i] == 0)
{
spf[i] = i;
for (int j = 2 * i; j < 100005; j += i)
{
// smallest prime factor of all
// multiples is i
if (spf[j] == 0)
spf[j] = i;
}
}
}
}
// Prime factorise n,
// and store prime factors in set s
static void factorize(int n, HashSet<Integer> s)
{
while (n > 1)
{
int z = spf[n];
s.add(z);
while (n % z == 0)
n /= z;
}
}
// for implementing DSU
static int []id = new int[100005];
static int []par = new int[100005];
static int []sizeContainer = new int[100005];
// root of component of node i
static int root(int i)
{
if (par[i] == i)
return i;
// finding root as well as applying
// path compression
else
return par[i] = root(par[i]);
}
// merging two components
static void merge(int a, int b)
{
// find roots of both components
int p = root(a);
int q = root(b);
// if already belonging to the same component
if (p == q)
return;
// Union by rank, the rank in this case is
// sizeContainer of the component.
// Smaller sizeContainer will be merged into
// larger, so the larger's root will be
// final root
if (sizeContainer[p] > sizeContainer[q])
{
p = p + q;
q = p - q;
p = p - q;
}
par[p] = q;
sizeContainer[q] += sizeContainer[p];
}
// Function to find the maximum sized container
static int maximumComponentsizeContainer(int a[],
int n)
{
// intitalise the parents,
// and component sizeContainer
for (int i = 0; i < 100005; i++)
{
// initially all component sizeContainers are 1
// ans each node it parent of itself
par[i] = i;
sizeContainer[i] = 1;
}
sieve();
for (int i = 0; i < n; i++)
{
// store prime factors of a[i] in s
HashSet<Integer> s = new HashSet<Integer>();
factorize(a[i], s);
for (int it : s)
{
// if this prime is seen as a factor
// for the first time
if (id[it] == 0)
id[it] = i + 1;
// if not then merge with that component
// in which this prime was previously seen
else
merge(i + 1, id[it]);
}
}
int answer = 0;
// maximum of sizeContainer of all components
for (int i = 0; i < n; i++)
answer = Math.max(answer, sizeContainer[i]);
return answer;
}
// Driver Code
public static void main(String[] args)
{
int n = 8;
int A[] = {2, 3, 6, 7,
4, 12, 21, 39};
System.out.print(
maximumComponentsizeContainer(A, n));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach # smallest prime factor spf = [0 for i in range(100005)] # Sieve of Eratosthenes def sieve(): for i in range(2, 100005): # is spf[i] = 0, then it's prime if (spf[i] == 0): spf[i] = i; for j in range(2 * i, 100005, i): # smallest prime factor of all # multiples is i if (spf[j] == 0): spf[j] = i; # Prime factorise n, # and store prime factors in set s def factorize(n, s): while (n > 1): z = spf[n]; s.add(z); while (n % z == 0): n //= z; # for implementing DSU id = [0 for i in range(100005)] par = [0 for i in range(100005)] sizeContainer = [0 for i in range(100005)] # root of component of node i def root(i): if (par[i] == i): return i; # finding root as well as applying # path compression else: return root(par[i]); return par[i] # merging two components def merge(a, b): # find roots of both components p = root(a); q = root(b); # if already belonging to the same component if (p == q): return; # Union by rank, the rank in this case is # sizeContainer of the component. # Smaller sizeContainer will be merged into # larger, so the larger's root will be # final root if (sizeContainer[p] > sizeContainer[q]): p = p + q; q = p - q; p = p - q; par[p] = q; sizeContainer[q] += sizeContainer[p]; # Function to find the maximum sized container def maximumComponentsizeContainer(a, n): # intitalise the parents, # and component sizeContainer for i in range(100005): # initially all component sizeContainers are 1 # ans each node it parent of itself par[i] = i; sizeContainer[i] = 1; sieve(); for i in range(n): # store prime factors of a[i] in s s = set() factorize(a[i], s); for it in s: # if this prime is seen as a factor # for the first time if (id[it] == 0): id[it] = i + 1; # if not then merge with that component # in which this prime was previously seen else: merge(i + 1, id[it]); answer = 0; # maximum of sizeContainer of all components for i in range(n): answer = max(answer, sizeContainer[i]); return answer; # Driver Code if __name__=='__main__': n = 8; A = [2, 3, 6, 7, 4, 12, 21, 39] print(maximumComponentsizeContainer(A, n)); # This code is contributed by Pratham76
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Smallest prime factor
static int []spf = new int[100005];
// Sieve of Eratosthenes
static void sieve()
{
for(int i = 2; i < 100005; i++)
{
// Is spf[i] = 0, then it's prime
if (spf[i] == 0)
{
spf[i] = i;
for(int j = 2 * i; j < 100005; j += i)
{
// Smallest prime factor of all
// multiples is i
if (spf[j] == 0)
spf[j] = i;
}
}
}
}
// Prime factorise n, and store
// prime factors in set s
static void factorize(int n, HashSet<int> s)
{
while (n > 1)
{
int z = spf[n];
s.Add(z);
while (n % z == 0)
n /= z;
}
}
// For implementing DSU
static int []id = new int[100005];
static int []par = new int[100005];
static int []sizeContainer = new int[100005];
// Root of component of node i
static int root(int i)
{
if (par[i] == i)
return i;
// Finding root as well as applying
// path compression
else
return par[i] = root(par[i]);
}
// Merging two components
static void merge(int a, int b)
{
// Find roots of both components
int p = root(a);
int q = root(b);
// If already belonging to
// the same component
if (p == q)
return;
// Union by rank, the rank in this case is
// sizeContainer of the component.
// Smaller sizeContainer will be merged into
// larger, so the larger's root will be
// readonly root
if (sizeContainer[p] > sizeContainer[q])
{
p = p + q;
q = p - q;
p = p - q;
}
par[p] = q;
sizeContainer[q] += sizeContainer[p];
}
// Function to find the maximum sized container
static int maximumComponentsizeContainer(int []a,
int n)
{
// Initialise the parents,
// and component sizeContainer
for(int i = 0; i < 100005; i++)
{
// Initially all component sizeContainers
// are 1 ans each node it parent of itself
par[i] = i;
sizeContainer[i] = 1;
}
sieve();
for(int i = 0; i < n; i++)
{
// Store prime factors of a[i] in s
HashSet<int> s = new HashSet<int>();
factorize(a[i], s);
foreach(int it in s)
{
// If this prime is seen as a factor
// for the first time
if (id[it] == 0)
id[it] = i + 1;
// If not then merge with that component
// in which this prime was previously seen
else
merge(i + 1, id[it]);
}
}
int answer = 0;
// Maximum of sizeContainer of all components
for(int i = 0; i < n; i++)
answer = Math.Max(answer, sizeContainer[i]);
return answer;
}
// Driver Code
public static void Main(String[] args)
{
int n = 8;
int []A = { 2, 3, 6, 7,
4, 12, 21, 39 };
Console.Write(
maximumComponentsizeContainer(A, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// smallest prime factor
var spf = Array(100005).fill(0);
// Sieve of Eratosthenes
function sieve()
{
for (var i = 2; i < 100005; i++) {
// is spf[i] = 0, then it's prime
if (spf[i] == 0) {
spf[i] = i;
for (var j = 2 * i; j < 100005; j += i) {
// smallest prime factor of all multiples is i
if (spf[j] == 0)
spf[j] = i;
}
}
}
}
// Prime factorise n,
// and store prime factors in set s
function factorize(n, s)
{
while (n > 1) {
var z = spf[n];
s.add(z);
while (n % z == 0)
n = parseInt(n/z);
}
return s;
}
// for implementing DSU
var id = Array(100005).fill(0);
var par =Array(100005).fill(0);
var sizeContainer = Array(100005).fill(0);
// root of component of node i
function root(i)
{
if (par[i] == i)
return i;
// finding root as well as applying
// path compression
else
return par[i] = root(par[i]);
}
// merging two components
function merge(a, b)
{
// find roots of both components
var p = root(a);
var q = root(b);
// if already belonging to the same component
if (p == q)
return;
// Union by rank, the rank in this case is
// sizeContainer of the component.
// Smaller sizeContainer will be merged into
// larger, so the larger's root will be
// final root
if (sizeContainer[p] > sizeContainer[q])
{
[p, q] = [q, p]
}
par[p] = q;
sizeContainer[q] += sizeContainer[p];
}
// Function to find the maximum sized container
function maximumComponentsizeContainer(a, n)
{
// intitalise the parents,
// and component sizeContainer
for (var i = 0; i < 100005; i++) {
// initially all component sizeContainers are 1
// ans each node it parent of itself
par[i] = i;
sizeContainer[i] = 1;
}
sieve();
for (var i = 0; i < n; i++) {
// store prime factors of a[i] in s
var s = new Set();
s = factorize(a[i], s);
s.forEach(it => {
// if this prime is seen as a factor
// for the first time
if (id[it] == 0)
id[it] = i + 1;
// if not then merge with that component
// in which this prime was previously seen
else
merge(i + 1, id[it]);
});
}
var answer = 0;
// maximum of sizeContainer of all components
for (var i = 0; i < n; i++)
answer = Math.max(answer, sizeContainer[i]);
return answer;
}
// Driver Code
var n = 8;
var A = [2, 3, 6, 7, 4, 12, 21, 39];
document.write( maximumComponentsizeContainer(A, n));
</script>
Producción:
8
Complejidad de tiempo: O(N * log(max(A)))
Espacio Auxiliar: O(10 5 )