Given a graph consisting of N nodes and an array edges[][] denoting an edge from edges[i][0] with edges[i][1]. Given a node K, the task is to find the node which has the maximum number of common nodes with K.
Examples:
Input: K = 1, N = 4, edges = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {2, 4}}
Output: 4
Explanation: The graph formed by given edges is shown below.
Given K = 1, Adjacent nodes to all the nodes are below
1: 2, 3
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3
Clearly node 4 is having maximum common nodes with node 1. Therefore, 4 is the answer.
Input: K = 2, N = 3, edges = {{1, 2}, {1, 3}, {2, 3}}
Output: 3
Approach: This problem can be solved by using Breadth-First Search. Follow the steps below to solve the given problem.
- The idea is to use BFS with the source as a given node (level 0).
- Store all the neighbors of a given node in a list, let’s say al1 (level 1)
- Now maintain another list al2 and store each level in BFS and count the common elements of al1 with al2.
- Maintain variable max to maintain the count of maximum common friends and another variable mostAppnode to store answer of the given problem.
- Return mostAppnode.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// No. of nodesint V;// Adjacency Listsvector<vector<int> > adj;// Neighbours of given node stored in al1vector<int> al1;void create_Graph(int v){ V = v; adj = {}; for (int i = 0; i < v; ++i) adj.push_back({});}// Function to add an edge into the graphvoid addEdge(int v, int w){ adj[(v - 1)].push_back(w - 1); adj[(w - 1)].push_back(v - 1);}// find element in queuebool contains(queue<int> q, int n){ while (q.size()) { if (q.front() == n) return 1; q.pop(); } return false;}int BFS(int s){ // Mark all the vertices as not visited // (By default set as false) bool visited[V] = { 0 }; // Create a queue for BFS queue<int> queue; // Mark the current node // as visited and enqueue it visited[s] = true; queue.push(s); int c = 0; // Max common nodes with given node int max = 0; int mostAppnode = 0; // To store common nodes int count = 0; while (queue.size() != 0) { // Dequeue a vertex from queue s = queue.front(); queue.pop(); // Get all adjacent nodes // of the dequeued node // If a adjacent has // not been visited, then // mark it visited and enqueue it c++; vector<int> al2; int i = 0; while (i < adj[s].size()) { int n = adj[s][i]; if (c == 1) al1.push_back(n); else al2.push_back(n); // If node is not // visited and also not // present in queue. if (!visited[n] && !contains(queue, n)) { visited[n] = true; queue.push(n); } i++; } if (al2.size() != 0) { for (int frnd : al2) { if (find(al1.begin(), al1.end(), frnd) != al1.end()) count++; } if (count > max) { max = count; mostAppnode = s; } } } if (max != 0) return mostAppnode + 1; else return -1;}// Driver Codeint main(){ int N = 4; create_Graph(4); addEdge(1, 2); addEdge(1, 3); addEdge(2, 3); addEdge(3, 4); addEdge(2, 4); int K = 1; cout << (BFS(K - 1)) << endl;}// This code is contributed by rj13to. |
Java
// Java implementation of above approachimport java.io.*;import java.util.*;class Graph { // No. of nodes private int V; // Adjacency Lists private ArrayList<ArrayList<Integer> > adj; // Neighbours of given node stored in al1 ArrayList<Integer> al1 = new ArrayList<>(); // Constructor Graph(int v) { V = v; adj = new ArrayList<>(); for (int i = 0; i < v; ++i) adj.add(new ArrayList<Integer>()); } // Function to add an edge into the graph void addEdge(int v, int w) { adj.get(v - 1).add(w - 1); adj.get(w - 1).add(v - 1); } private int BFS(int s) { // Mark all the vertices as not visited // (By default set as false) boolean visited[] = new boolean[V]; // Create a queue for BFS LinkedList<Integer> queue = new LinkedList<Integer>(); // Mark the current node // as visited and enqueue it visited[s] = true; queue.add(s); int c = 0; // Max common nodes with given node int max = 0; int mostAppnode = 0; // To store common nodes int count = 0; while (queue.size() != 0) { // Dequeue a vertex from queue s = queue.poll(); // Get all adjacent nodes // of the dequeued node // If a adjacent has // not been visited, then // mark it visited and enqueue it c++; ArrayList<Integer> al2 = new ArrayList<>(); Iterator<Integer> i = adj.get(s).listIterator(); while (i.hasNext()) { int n = i.next(); if (c == 1) al1.add(n); else al2.add(n); // If node is not // visited and also not // present in queue. if (!visited[n] && !queue.contains(n)) { visited[n] = true; queue.add(n); } } if (al2.size() != 0) { for (int frnd : al2) { if (al1.contains(frnd)) count++; } if (count > max) { max = count; mostAppnode = s; } } } if (max != 0) return mostAppnode + 1; else return -1; } // Driver Code public static void main(String[] args) { int N = 4; Graph g = new Graph(4); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(3, 4); g.addEdge(2, 4); int K = 1; System.out.println(g.BFS(K - 1)); }} |
Python3
# python implementation of above approach# Neighbours of given node stored in al1al1 = []# Function to add an edge into the graphdef addEdge(v, w, adj): adj[v - 1].append(w - 1) adj[w - 1].append(v - 1)def BFS(s, adj, V): # Mark all the vertices as not visited # (By default set as false) visited = [False] * V # Create a queue for BFS queue = [] # Mark the current node # as visited and enqueue it visited[s] = True queue.append(s) c = 0 # Max common nodes with given node max = 0 mostAppnode = 0 # To store common nodes count = 0 while (len(queue) != 0): # Dequeue a vertex from queue s = queue[0] queue.pop(0) # Get all adjacent nodes # of the dequeued node # If a adjacent has # not been visited, then # mark it visited and enqueue it c += 1 al2 = [] for i in adj[s]: n = i if (c == 1): al1.append(n) else: al2.append(n) # If node is not # visited and also not # present in queue. is_contained = False if(n in queue): is_contained = True if ((visited[n] == False) and (is_contained == False)): visited[n] = True queue.append(n) if (len(al2) != 0): for frnd in al2: if (frnd in al1): count += 1 if (count > max): max = count mostAppnode = s if (max != 0): return mostAppnode + 1 else: return -1# Driver CodeN = 4# list to store connectionsadj = [[]]*NaddEdge(1, 2, adj)addEdge(1, 3, adj)addEdge(2, 3, adj)addEdge(3, 4, adj)addEdge(2, 4, adj)K = 1print(BFS(K - 1, adj, N))# This code is contributed by rj13to. |
C++
#include <iostream>using namespace std;int main() { cout << "GFG!"; return 0;} |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ // No. of nodes static int V; // Adjacency Lists static List<List<int>> adj = new List<List<int>>(); // Neighbours of given node stored in al1 static List<int> al1 = new List<int>(); static void CreateGraph(int v) { V = v; adj = new List<List<int>>(); for (int i = 0; i < v; i++) { adj.Add(new List<int>()); } } // Function to add an edge into the graph static void AddEdge(int v, int w) { adj[(v - 1)].Add(w - 1); adj[(w - 1)].Add(v - 1); } // find element in queue static bool Contains(Queue<int> q, int n) { while (q.Count > 0) { if (q.Peek() == n) return true; q.Dequeue(); } return false; } static int BFS(int s) { // Mark all the vertices as not visited // (By default set as false) bool[] visited = new bool[V]; // Create a queue for BFS Queue<int> queue = new Queue<int>(); // Mark the current node // as visited and enqueue it visited[s] = true; queue.Enqueue(s); int c = 0; // Max common nodes with given node int max = 0; int mostAppnode = 0; // To store common nodes int count = 0; while (queue.Count > 0) { // Dequeue a vertex from queue s = queue.Dequeue(); // Get all adjacent nodes // of the dequeued node // If a adjacent has // not been visited, then // mark it visited and enqueue it c++; List<int> al2 = new List<int>(); int i = 0; while (i < adj[s].Count) { int n = adj[s][i]; if (c == 1) al1.Add(n); else al2.Add(n); // If node is not // visited and also not // present in queue. if (!visited[n] && !Contains(queue, n)) { visited[n] = true; queue.Enqueue(n); } i++; } if (al2.Count > 0) { for (int frnd : al2) { if (al1.Contains(frnd)) count++; } if (count > max) { max = count; mostAppnode = s; } } } if |
Javascript
// JavaScript implementation of the C++ code above// No. of nodeslet V;// Adjacency Listslet adj = [];// Neighbours of given node stored in al1let al1 = [];function create_Graph(v) { V = v; adj = []; for (let i = 0; i < v; ++i) adj.push([]);}// Function to add an edge into the graphfunction addEdge(v, w) { adj[(v - 1)].push(w - 1); adj[(w - 1)].push(v - 1);}// find element in queuefunction contains(q, n) { while (q.length) { if (q.shift() === n) return true; } return false;}function BFS(s) { // Mark all the vertices as not visited // (By default set as false) let visited = new Array(V).fill(false); // Create a queue for BFS let queue = []; // Mark the current node // as visited and enqueue it visited[s] = true; queue.push(s); let c = 0; // Max common nodes with given node let max = 0; let mostAppnode = 0; // To store common nodes let count = 0; while (queue.length !== 0) { // Dequeue a vertex from queue s = queue.shift(); // Get all adjacent nodes // of the dequeued node // If a adjacent has // not been visited, then // mark it visited and enqueue it c++; let al2 = []; let i = 0; while (i < adj[s].length) { let n = adj[s][i]; if (c === 1) al1.push(n); else al2.push(n); // If node is not // visited and also not // present in queue. if (!visited[n] && !contains(queue, n)) { visited[n] = true; queue.push(n); } i++; } if (al2.length !== 0) { for (let frnd of al2) { if (al1.includes(frnd)) count++; } if (count > max) { max = count; mostAppnode = s; } } } if (max !== 0) return mostAppnode + 1; else return -1;}// Driver Codelet N = 4;create_Graph(4);addEdge(1, 2);addEdge(1, 3);addEdge(2, 3);addEdge(3, 4);addEdge(2, 4);let K = 1;console.log(BFS(K - 1)); |
Output
4
Time Complexity: O (V*V), BFS will take O(V+E) time but finding common elements between al1 and al2 will take O(V*V) time.
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
