Dado un gráfico G(V, E) , divídalo en dos conjuntos de manera que no haya dos vértices en un conjunto conectados directamente. Si no es posible, escriba «No posible».
Ejemplos:
Entrada: V = 7, E = 6,
Flanco = {{1, 2}, {2, 3}, {3, 4}, {3, 6}, {5, 6}, {6, 7}}
Salida :
7 5 1 3
6 2 4
Explicación : el Node {7, 5, 1, 3} no está conectado directamente y los Nodes {6, 2, 4} no están conectados directamente
. Entrada: V = 3, E = 3,
Flanco = {{1, 2}, {2, 3}, {3, 1}}
Salida: No es posible
Explicación: No se puede dividir en dos partes
Enfoque: La idea es usar dos conjuntos, digamos ( U y V ) y recorrer el gráfico de manera BFS . Recorra cada vértice, márquelo como visitado, verifique si los vértices vecinos están presentes en los conjuntos o no. De lo contrario, insértelo en el conjunto opuesto al actual. En caso afirmativo, si están en el mismo conjunto, devuelva falso. Siga los pasos a continuación para resolver el problema:
- Defina una función bipartita() y realice las siguientes tareas:
- Si V es igual a 0 , devuelve verdadero.
- De lo contrario, realice el BFS para verificar si los vecinos pertenecen al conjunto opuesto o no.
- Inicialice la variable booleana res como verdadera.
- Inicializa el vector visitado[V+1] con valores falsos.
- Itere sobre el rango [1, V] usando la variable i y realice las siguientes tareas:
- Si visited[i] es falso , establezca el valor de res como bit a bit Y de res y bipartito() donde la función verifica si es posible dividir.
- Después de realizar los pasos anteriores, imprima la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Unordered sets to store ans
unordered_set<int> sets[2];
// Function to divide a graph into two sets,
// returns true if possible otherwise false
bool bipartite(vector<vector<int> >& edges,
int V, int i,
vector<bool>& visited)
{
if (V == 0) {
return true;
}
vector<int> pending;
// Inserting source vertex in U(set[0])
sets[0].insert(i);
// Enqueue source vertex
pending.push_back(i);
while (pending.size() > 0) {
// Dequeue current vertex
int current = pending.back();
// Mark the current vertex true
visited[current] = true;
pending.pop_back();
// Finding the set of
// current vertex(parent vertex)
int currentSet
= sets[0].count(current)
> 0
? 0
: 1;
for (int i = 0; i
< edges[current].size();
i++) {
// Picking out neighbour
// of current vertex
int neighbor = edges[current][i];
// If not present
// in any of the set
if (sets[0].count(neighbor) == 0
&& sets[1].count(neighbor) == 0) {
// Inserting in opposite
// of current vertex
sets[1 - currentSet].insert(neighbor);
pending.push_back(neighbor);
}
// Else if present in the same
// current vertex set the partition
// is not possible
else if (sets[currentSet].count(neighbor)
> 0) {
return false;
}
}
}
return true;
}
bool possibleBipartition(int V,
vector<vector<int> >& G)
{
// To store graph as adjacency list in edges
vector<vector<int> > edges(V + 1);
for (auto v : G) {
edges[v[0]].push_back(v[1]);
edges[v[1]].push_back(v[0]);
}
vector<bool> visited(V + 1, false);
bool res = true;
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
res = res and bipartite(edges, V,
i, visited);
}
}
return res;
}
// Driver Code
int main()
{
int V = 7, E = 6;
vector<vector<int> > G
= { { 1, 2 }, { 2, 3 }, { 3, 4 },
{ 3, 6 }, { 5, 6 }, { 6, 7 } };
// If partition is possible
if (possibleBipartition(V, G)) {
for (auto elem : sets[0]) {
cout << elem << " ";
}
cout << "\n";
for (auto elem : sets[1]) {
cout << elem << " ";
}
}
// If partition is not possible
else
cout << "Not Possible";
return 0;
}
7 5 1 3 6 2 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)