Dado un grafo g no dirigido , la tarea es encontrar el número de coaliciones formadas en él después de eliminar los vértices Q y el máximo de vértices entre todos estos componentes conectados.
Una coalición se define como el número de componentes conectados que quedan después de eliminar los vértices Q , es decir, los vértices que se eliminan del gráfico no se consideran parte de la coalición.
Ejemplo:
Entrada: V = 7, E = 6, Q = 1
Bordes: { {0, 3}, {1, 5}, {3, 6}, {3, 2}, {2, 4}, {5, 6} }
consultas: {3}
Salida: 3 3
Explicación:Si eliminamos los vértices 3 del gráfico, sus aristas correspondientes {{0, 3}, {3, 6}, {3, 2}} también se eliminarán del gráfico y el número de componentes conectados excluyendo Q (eliminado vértices) son {0}. {1, 5, 6} y {2, 4} con una coalición máxima de {1, 5, 6} como 3.
Entrada: V = 6, E = 6, Q = 2
Bordes: {{0, 3}, {0, 2}, {3, 4}, {3, 5}, {3, 1}, {2, 4}}
consultas: {1, 2}
Salida: 1 4
Explicación: cuando se eliminan los vértices 1 y 2 del gráfico dado, el componente conectado que excluye a Q es {0, 3, 4, 5} con una coalición máxima de {0, 3, 4, 5} como 4.
Enfoque: El enfoque para resolver este problema basado en la siguiente idea
La idea aquí es que, si eliminamos todos los bordes innecesarios que se conectan con el vértice mencionado en la consulta, el problema se resolverá para encontrar el número de componentes conectados en el gráfico no dirigido .
Basado en la idea anterior, siga los pasos a continuación para implementar este enfoque:
- Podemos usar el mapa múltiple para almacenar bordes entre los vértices.
- Eliminamos todos los bordes que están conectados con los vértices (porque asumimos que tendremos que eliminar todos los vértices de la Consulta entonces, también se deben eliminar sus bordes correspondientes que están conectados con los vértices)
- Encuentre el número de componentes conectados en el gráfico no dirigido .
- Use una variable count para almacenar el número de componentes conectados, cnt para contar el número de vértices del componente que estamos recorriendo y maxLen para almacenar el máximo de vértices entre todos los componentes (máximo de cnt ).
- Calcular coaliciones = recuento (número de componentes conectados) – tamaño de la consulta (número de vértices eliminados)
A continuación se muestra la implementación del enfoque anterior:
C++14
#include <bits/stdc++.h>
using namespace std;
int maxLen = 0;
int cnt;
class Graph {
int V;
list<int>* adj;
multimap<int, int> adj2;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdges();
void removeEdges(int V, int Edges[][2],
int E, int queries[],
int Q);
int NumberOfconnectedComponents();
};
// function to find the number of connected
// component in undirected graph
int Graph::NumberOfconnectedComponents()
{
bool* visited = new bool[V];
int count = 0;
for (int v = 0; v < V; v++)
visited[v] = false;
for (int v = 0; v < V; v++) {
if (visited[v] == false) {
cnt = 0;
DFSUtil(v, visited);
count += 1;
}
}
return count;
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cnt++;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i]) {
DFSUtil(*i, visited);
}
maxLen = max(maxLen, cnt);
}
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// add Edges in the graph
void Graph::addEdges()
{
for (auto x : adj2) {
adj[x.first].push_back(x.second);
adj[x.second].push_back(x.first);
}
}
// function to remove all the edges that are
// connected with vertices
void Graph::removeEdges(int V, int Edges[][2],
int E, int queries[],
int Q)
{
multimap<int, int> adj3;
for (int i = 0; i < E; i++)
adj3.insert({ Edges[i][0], Edges[i][1] });
for (int i = 0; i < Q; i++) {
auto it1 = adj3.lower_bound(queries[i]);
auto it2 = adj3.upper_bound(queries[i]);
adj3.erase(it1, it2);
}
for (auto it = adj3.begin(); it != adj3.end(); it++) {
adj2.insert({ it->second, it->first });
}
for (int i = 0; i < Q; i++) {
auto it1 = adj2.lower_bound(queries[i]);
auto it2 = adj2.upper_bound(queries[i]);
adj2.erase(it1, it2);
}
}
// Driver code
int main()
{
int V = 7, E = 6;
Graph g(V);
int Edges[][2] = { { 0, 3 }, { 1, 5 }, { 3, 6 }, { 3, 2 }, { 2, 4 }, { 5, 6 } };
int Q = 1;
int queries[] = { 3 };
// remove all the edges that are connected with
// vertices given in the queries
g.removeEdges(V, Edges, E, queries, Q);
g.addEdges();
cout << g.NumberOfconnectedComponents() - Q;
cout << " " << maxLen;
return 0;
}
3 3
Complejidad temporal: O(V + E*log(E)), donde V es el número de vértices y E es el número de aristas del gráfico.
Espacio Auxiliar: O(V), ya que se requiereun arreglo extra visitado de tamaño V.
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA