Count of connected components in given graph after removal of given Q vertices
Given an undirected graph g, the task is to find the number of coalitions formed in it after the removal of Q vertices and maximum vertices among all these connected components.
A coalition is defined as the number of connected components left after removal of Q vertices i.e vertices being removed from the graph are not considered as part of the coalition.
Example:
Input: V = 7, E = 6, Q = 1
Edges: { {0, 3}, {1, 5}, {3, 6}, {3, 2}, {2, 4}, {5, 6} }
queries: {3}
Output: 3 3
Explanation:If we remove vertices 3 from the graph then their corresponding edges {{0, 3}, {3, 6}, {3, 2}} will also be get removed from the graph and the number of the connected components excluding Q (removed vertices) are {0}. {1, 5, 6} and {2, 4} with maximum coalition of {1, 5, 6} as 3.
Input: V = 6, E = 6, Q = 2
Edges: {{0, 3}, {0, 2}, {3, 4}, {3, 5}, {3, 1}, {2, 4}}
queries: {1, 2}
Output: 1 4
Explanation: When vertex 1 and 2 is removed from the given graph the connected component excluding Q is {0, 3, 4, 5} with maximum coalition of {0, 3, 4, 5} as 4.
Approach: The approach to solve this problem based on following idea
The idea here is, if we remove all unnecessary edges that connects with the vertex mentioned in the query, then the problem will break down to find the number of connected component in undirected graph.
Based on above idea follow the steps below to implement this approach:
- We can use the multimap to store edges between the vertices.
- We remove all edges that are connected with the vertices (because we assume that we will have to delete all the vertices from the Query then, their corresponding edges should also be get remove that are connected with the vertices)
- Find the number of connected component in undirected graph.
- Use a variable count to store the number of connected components, cnt to keep count of number of vertices of the component we are traversing and maxLen to store maximum vertices among all components ( maximum of cnt ).
- Calculate coalitions = count ( number of connected components ) – size of query ( number of vertices removed)
Below is the implementation of the above approach:
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; } |
Java
// Java code addition for the above approach import java.io.*; import java.util.*; class Graph { private int V; private List<Integer>[] adj; private TreeMap<Integer, Integer> adj2; public int maxLen = 0 ; public int cnt; public Graph( int V) { this .V = V; adj = new List[V]; for ( int i = 0 ; i < V; i++) adj[i] = new ArrayList<>(); adj2 = new TreeMap<>(); } // add Edges in the graph public void addEdges() { for (Map.Entry<Integer, Integer> entry : adj2.entrySet()) { int key = entry.getKey(); int value = entry.getValue(); adj[key].add(value); adj[value].add(key); } } // Function to remove all the edges that are connected // with vertices public void removeEdges( int V, int [][] Edges, int E, int [] queries, int Q) { TreeMap<Integer, Integer> adj3 = new TreeMap<>(); for ( int i = 0 ; i < E; i++) adj3.put(Edges[i][ 0 ], Edges[i][ 1 ]); for ( int i = 0 ; i < Q; i++) adj3.remove(queries[i]); for (Map.Entry<Integer, Integer> it : adj3.entrySet()) adj2.put(it.getValue(), it.getKey()); for ( int i = 0 ; i < Q; i++) adj2.remove(queries[i]); } // Function to find the number of connected component in // undirected graph public int numberOfConnectedComponents() { boolean [] visited = new boolean [V]; int count = 0 ; for ( int v = 0 ; v < V; v++) visited[v] = false ; for ( int v = 0 ; v < V; v++) { if (!visited[v]) { cnt = 0 ; DFSUtil(v, visited); count += 1 ; } } return count; } public void DFSUtil( int v, boolean [] visited) { visited[v] = true ; cnt++; for ( int i : adj[v]) { if (!visited[i]) DFSUtil(i, visited); } maxLen = Math.max(maxLen, cnt); } } class GFG { public static void main(String[] args) { int V = 7 , E = 6 ; Graph g = new Graph(V); int [][] Edges = { { 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(); System.out.println(g.numberOfConnectedComponents() - Q + " " + g.maxLen); } } // This code is contributed by karthik |
Python3
from collections import defaultdict class Graph: def __init__( self , V): self .V = V self .adj = defaultdict( list ) self .adj2 = {} #add Edges in the graph def add_edges( self ): for x in self .adj2: self .adj[x[ 0 ]].append(x[ 1 ]) self .adj[x[ 1 ]].append(x[ 0 ]) def remove_edges( self , V, Edges, E, queries, Q): adj3 = {} for i in range (E): adj3[Edges[i][ 0 ]] = Edges[i][ 1 ] for i in range (Q): adj3.pop(queries[i], None ) for it in adj3.items(): self .adj2[it[ 1 ], it[ 0 ]] = True for i in range (Q): self .adj2.pop(queries[i], None ) def number_of_connected_components( self ): visited = [ False ] * self .V count = 0 max_len = 0 def DFS_util(v, visited, cnt): nonlocal max_len visited[v] = True cnt[ 0 ] + = 1 for i in self .adj[v]: if not visited[i]: DFS_util(i, visited, cnt) max_len = max (max_len, cnt[ 0 ]) for v in range ( self .V): if not visited[v]: cnt = [ 0 ] DFS_util(v, visited, cnt) count + = 1 return count, max_len #Driver code V = 7 E = 6 g = Graph(V) Edges = [ [ 0 , 3 ], [ 1 , 5 ], [ 3 , 6 ], [ 3 , 2 ], [ 2 , 4 ], [ 5 , 6 ] ] Q = 1 queries = [ 3 ] # remove all the edges that are connected with vertices given in the queries g.remove_edges(V, Edges, E, queries, Q) g.add_edges() result = g.number_of_connected_components() print (result[ 0 ], result[ 1 ]) |
C#
//C# code for the above approach using System; using System.Collections.Generic; public class Graph { private int V; private List< int >[] adj; private SortedDictionary< int , int > adj2; public Graph( int V) { this .V = V; adj = new List< int >[V]; for ( int i = 0; i < V; i++) adj[i] = new List< int >(); adj2 = new SortedDictionary< int , int >(); } public void addEdges() { foreach (KeyValuePair< int , int > x in adj2) { adj[x.Key].Add(x.Value); adj[x.Value].Add(x.Key); } } // function to remove all the edges that are // connected with vertices public void removeEdges( int V, int [,] Edges, int E, int [] queries, int Q) { SortedDictionary< int , int > adj3 = new SortedDictionary< int , int >(); for ( int i = 0; i < E; i++) adj3[Edges[i, 0]] = Edges[i, 1]; for ( int i = 0; i < Q; i++) adj3.Remove(queries[i]); foreach (KeyValuePair< int , int > it in adj3) adj2[it.Value] = it.Key; for ( int i = 0; i < Q; i++) adj2.Remove(queries[i]); } public int 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]) { cnt = 0; DFSUtil(v, visited); count += 1; } } return count; } public int maxLen = 0; public int cnt; public void DFSUtil( int v, bool [] visited) { visited[v] = true ; cnt++; foreach ( int i in adj[v]) { if (!visited[i]) DFSUtil(i, visited); } maxLen = Math.Max(maxLen, cnt); } } public class Program { // Driver code public static void Main() { int V = 7, E = 6; Graph g = new Graph(V); int [,] Edges = { { 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(); Console.WriteLine(g.NumberOfconnectedComponents() - Q + " " + g.maxLen); } } |
Javascript
// JavaScript code for the above approach class Graph { constructor(V) { this .V = V; this .adj = new Array(V); for (let i = 0; i < V; i++) { this .adj[i] = []; } this .adj2 = new Map(); this .maxLen = 0; this .cnt = 0; } // add Edges in the graph addEdges() { for (let [key, value] of this .adj2) { this .adj[key].push(value); this .adj[value].push(key); } } // Function to remove all the edges that are connected with vertices removeEdges(V, Edges, E, queries, Q) { let adj3 = new Map(); for (let i = 0; i < E; i++) { adj3.set(Edges[i][0], Edges[i][1]); } for (let i = 0; i < Q; i++) { adj3. delete (queries[i]); } for (let [key, value] of adj3) { this .adj2.set(value, key); } for (let i = 0; i < Q; i++) { this .adj2. delete (queries[i]); } } // Function to find the number of connected component in undirected graph numberOfConnectedComponents() { let visited = new Array( this .V).fill( false ); let count = 0; for (let v = 0; v < this .V; v++) { if (!visited[v]) { this .cnt = 0; this .DFSUtil(v, visited); count += 1; } } return count; } DFSUtil(v, visited) { visited[v] = true ; this .cnt++; for (let i of this .adj[v]) { if (!visited[i]) { this .DFSUtil(i, visited); } } this .maxLen = Math.max( this .maxLen, this .cnt); } } let V = 7, E = 6; let g = new Graph(V); let Edges = [[0, 3], [1, 5], [3, 6], [3, 2], [2, 4], [5, 6]]; let Q = 1; let queries = [3]; // remove all the given edges that are connected with vertices // given in the queries g.removeEdges(V, Edges, E, queries, Q); g.addEdges(); console.log(g.numberOfConnectedComponents() - Q + " " + g.maxLen); // This code is contributed by sankar. |
3 3
Time complexity: O(V + E*log(E)), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V), since an extra visited array of size V is required.