Dado un número entero N , que representa el número de Nodes presentes en un gráfico no dirigido, con cada Node valorado de 1 a N, y una array 2D Edges[][] , que representa el par de vértices conectados por un borde, la tarea es encontrar un conjunto de como máximo N/2 Nodes tales que los Nodes que no están presentes en el conjunto, están conectados adyacentes a cualquiera de los Nodes presentes en el conjunto.
Ejemplos:
Entrada: N = 4, Edges[][2] = {{2, 3}, {1, 3}, {4, 2}, {1, 2}}
Salida: 3 2
Explicación: Conexiones especificadas en el gráfico anterior son los siguientes:
1
/ \
2 – 3
|
4
La selección del conjunto {2, 3} satisface las condiciones requeridas.Entrada: N = 5, Bordes[][2] = {{2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3}, {5, 1}, {5, 2}, {5, 3}, {5, 4}}
Salida: 1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Suponga que un Node es el Node de origen , entonces la distancia de cada vértice desde el Node de origen será par o impar .
- Divida los Nodes en dos conjuntos diferentes según la paridad, el tamaño de al menos uno de los conjuntos no excederá N/2 . Dado que cada Node de cierta paridad está conectado con al menos un Node de paridad opuesta, se cumple el criterio de elegir como máximo N/2 Nodes.
Siga los pasos a continuación para resolver el problema:
- Suponga que cualquier vértice es el Node de origen .
- Inicialice dos conjuntos , digamos evenParity y oddParity, para almacenar los Nodes que tienen distancias pares e impares desde el Node de origen, respectivamente.
- Realice BFS Traversal en el gráfico dado y divida los vértices en dos conjuntos diferentes según la paridad de sus distancias desde la fuente :
- Si la distancia de cada Node conectado desde el Node de origen es impar, inserte el Node actual en el conjunto oddParity .
- Si la distancia de cada Node conectado desde el Node de origen es par, inserte el Node actual en el conjunto evenParity .
- Después de completar los pasos anteriores, imprima los elementos del conjunto con el tamaño mínimo.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to add an edge
// to the adjacency list
void addEdge(vector<vector<int> >& adj,
int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Function to perform BFS
// traversal on a given graph
vector<vector<int> > BFS(
int N, int source,
vector<vector<int> > adjlist)
{
// Stores the distance of each
// node from the source node
int dist[N + 1];
vector<vector<int> > vertex_set;
// Update the distance of all
// vertices from source as -1
memset(dist, -1, sizeof dist);
// Assign two separate vectors
// for parity odd and even parities
vertex_set.assign(2, vector<int>(0));
// Perform BFS Traversal
queue<int> Q;
// Push the source node
Q.push(source);
dist = 0;
// Iterate until queue becomes empty
while (!Q.empty()) {
// Get the front node
// present in the queue
int u = Q.front();
Q.pop();
// Push the node into vertex_set
vertex_set[dist[u] % 2].push_back(u);
// Check if the adjacent
// vertices are visited
for (int i = 0;
i < (int)adjlist[u].size(); i++) {
// Adjacent node
int v = adjlist[u][i];
// If the node v is unvisited
if (dist[v] == -1) {
// Update the distance
dist[v] = dist[u] + 1;
// Enqueue the node v
Q.push(v);
}
}
}
// Return the possible set of nodes
return vertex_set;
}
// Function to find a set of vertices
// of at most N/2 nodes such that each
// unchosen node is connected adjacently
// to one of the nodes in the set
void findSet(int N,
vector<vector<int> > adjlist)
{
// Source vertex
int source = 1;
// Store the vertex set
vector<vector<int> > vertex_set
= BFS(N, source, adjlist);
// Stores the index
// with minimum size
int in = 0;
if (vertex_set[1].size()
< vertex_set[0].size())
in = 1;
// Print the nodes present in the set
for (int node : vertex_set[in]) {
cout << node << " ";
}
}
// Driver Code
int main()
{
int N = 5;
int M = 8;
vector<vector<int> > adjlist;
adjlist.assign(N + 1, vector<int>(0));
// Graph Formation
addEdge(adjlist, 2, 5);
addEdge(adjlist, 2, 1);
addEdge(adjlist, 5, 1);
addEdge(adjlist, 4, 5);
addEdge(adjlist, 1, 4);
addEdge(adjlist, 2, 4);
addEdge(adjlist, 3, 4);
addEdge(adjlist, 3, 5);
// Function Call to print the
// set of at most N / 2 nodes
findSet(N, adjlist);
return 0;
}
Python3
# Python3 program for the above approach from collections import deque # Function to add an edge # to the adjacency list def addEdge(adj, u, v): adj[u].append(v) adj[v].append(u) return adj # Function to perform BFS # traversal on a given graph def BFS(N, source, adjlist): # Stores the distance of each # node from the source node dist = [-1]*(N + 1) vertex_set = [[] for i in range(2)] # Perform BFS Traversal Q = deque() # Push the source node Q.append(source) dist = 0 # Iterate until queue becomes empty while len(Q) > 0: # Get the front node # present in the queue u = Q.popleft() # Push the node into vertex_set vertex_set[dist[u] % 2].append(u) # Check if the adjacent # vertices are visited for i in range(len(adjlist[u])): # Adjacent node v = adjlist[u][i] # If the node v is unvisited if (dist[v] == -1): # Update the distance dist[v] = dist[u] + 1 # Enqueue the node v Q.append(v) # Return the possible set of nodes return vertex_set # Function to find a set of vertices # of at most N/2 nodes such that each # unchosen node is connected adjacently # to one of the nodes in the set def findSet(N, adjlist): # Source vertex source = 1 # Store the vertex set vertex_set = BFS(N, source, adjlist) # Stores the index # with minimum size inn = 0 if (len(vertex_set[1]) < len(vertex_set[0])): inn = 1 # Print the nodes present in the set for node in vertex_set[inn]: print(node, end=" ") # Driver Code if __name__ == '__main__': N = 5 M = 8 adjlist = [[] for i in range(N+1)] # Graph Formation adjlist = addEdge(adjlist, 2, 5) adjlist = addEdge(adjlist, 2, 1) adjlist = addEdge(adjlist, 5, 1) adjlist = addEdge(adjlist, 4, 5) adjlist = addEdge(adjlist, 1, 4) adjlist = addEdge(adjlist, 2, 4) adjlist = addEdge(adjlist, 3, 4) adjlist = addEdge(adjlist, 3, 5) # Function Call to print the # set of at most N / 2 nodes findSet(N, adjlist) # This code is contributed by mohit kumar 29.
Producción:
1 3
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)