Given Adjacency List representation of a tree and an integer K., the task is to find whether the given tree can be split into K equal Connected Components or not.
Note: Two connected components are said to be equal if they contain equal number of nodes.
Examples:
Input: N = 15, K = 5
Below is the given tree with Number nodes = 15
Output: YES
Explanation:
Below is the 5 number of Connected Components can be made:
Approach:
The idea is to use Depth First Search(DFS) traversal on the given tree of N nodes to find whether the given tree can be split into K equal Connected Components or not. Following are the steps:
- Start DFS Traversal with the root of the tree.
- For every vertex not visited during DFS traversal, recursively call DFS for that vertex keeping the count of nodes traverse during every DFS recursive call.
- If the count of nodes is equals to (N/K) then we got our one of the set of Connected Components.
- If the total number of the set of Connected Components of (N/K) nodes is equal to K. Then the given graph can be split into K equals Connected Components.
Below is the implementation of the above approach:
C++
// C++ program to detect whether// the given Tree can be split// into K equals components#include <bits/stdc++.h>using namespace std;// For checking if the graph// can be split into K equal// Connected Componentsint flag = 0;// DFS Traversalint DFS(vector<int> adj[], int k, int i, int x){ // Initialise ans to 1 int ans = 1; // Traverse the adjacency // for vertex i for (auto& it : adj[i]) { if (it != k) { ans += DFS(adj, i, it, x); } } // If number of nodes is // greater than x, then // the tree cannot be split if (ans > x) { flag = 1; return 0; } // Check for requirement // of nodes else if (ans == x) { ans = 0; } return ans;}// A utility function to add// an edge in an undirected// Treevoid addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Driver's Codeint main(){ int N = 15, K = 5; // Adjacency List vector<int> adj[N + 1]; // Adding edges to List addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 2, 4); addEdge(adj, 4, 5); addEdge(adj, 5, 6); addEdge(adj, 5, 7); addEdge(adj, 4, 8); addEdge(adj, 4, 9); addEdge(adj, 8, 11); addEdge(adj, 10, 11); addEdge(adj, 11, 14); addEdge(adj, 9, 12); addEdge(adj, 12, 15); addEdge(adj, 12, 13); // Check if tree can be split // into K Connected Components // of equal number of nodes if (N % K == 0) { // DFS call to Check // if tree can be split DFS(adj, -1, 1, N / K); } // If flag is 0, then the // given can be split to // Connected Components cout << (flag ? "NO" : "YES"); return 0;} |
Java
// Java program to detect whether// the given Tree can be split// into K equals componentsimport java.util.*;class GFG{ // For checking if the graph// can be split into K equal// Connected Componentsstatic int flag = 0; // DFS Traversalstatic int DFS(Vector<Integer> adj[], int k, int i, int x){ // Initialise ans to 1 int ans = 1; // Traverse the adjacency // for vertex i for (int it : adj[i]) { if (it != k) { ans += DFS(adj, i, it, x); } } // If number of nodes is // greater than x, then // the tree cannot be split if (ans > x) { flag = 1; return 0; } // Check for requirement // of nodes else if (ans == x) { ans = 0; } return ans;} // A utility function to add// an edge in an undirected// Treestatic void addEdge(Vector<Integer> adj[], int u, int v){ adj[u].add(v); adj[v].add(u);} // Driver's Codepublic static void main(String[] args){ int N = 15, K = 5; // Adjacency List Vector<Integer> []adj = new Vector[N + 1]; for(int i= 0; i < N + 1; i++) adj[i] = new Vector<Integer>(); // Adding edges to List addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 2, 4); addEdge(adj, 4, 5); addEdge(adj, 5, 6); addEdge(adj, 5, 7); addEdge(adj, 4, 8); addEdge(adj, 4, 9); addEdge(adj, 8, 11); addEdge(adj, 10, 11); addEdge(adj, 11, 14); addEdge(adj, 9, 12); addEdge(adj, 12, 15); addEdge(adj, 12, 13); // Check if tree can be split // into K Connected Components // of equal number of nodes if (N % K == 0) { // DFS call to Check // if tree can be split DFS(adj, -1, 1, N / K); } // If flag is 0, then the // given can be split to // Connected Components System.out.print(flag==1 ? "NO" : "YES"); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to detect whether # the given Tree can be split # into K equals components# For checking if the graph # can be split into K equal # Connected Components flag = 0# DFS Traversal def DFS(adj, k, i, x): # Initialise ans to 1 ans = 1 # Traverse the adjacency # for vertex i for it in adj[i]: if it is not k: ans += DFS(adj, i, it, x) # If number of nodes is # greater than x, then # the tree cannot be split if (ans > x): flag = 1 return 0 # Check for requirement # of nodes elif (ans == x): ans = 0 return ans# A utility function to add # an edge in an undirected # Tree def addEdge(adj, u, v): adj[u].append(v) adj[v].append(u)# Driver codeif __name__=="__main__": (N, K) = (15, 5) # Adjacency List adj = [[] for i in range(N + 1)] # Adding edges to List addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 2, 4); addEdge(adj, 4, 5); addEdge(adj, 5, 6); addEdge(adj, 5, 7); addEdge(adj, 4, 8); addEdge(adj, 4, 9); addEdge(adj, 8, 11); addEdge(adj, 10, 11); addEdge(adj, 11, 14); addEdge(adj, 9, 12); addEdge(adj, 12, 15); addEdge(adj, 12, 13); # Check if tree can be split # into K Connected Components # of equal number of nodes if (N % K == 0): # DFS call to Check # if tree can be split DFS(adj, -1, 1, N // K) # If flag is 0, then the # given can be split to # Connected Components if flag == 1: print("NO") else: print("YES")# This code is contributed by rutvik_56 |
C#
// C# program to detect whether// the given Tree can be split// into K equals componentsusing System;using System.Collections.Generic;class GFG{ // For checking if the graph// can be split into K equal// Connected Componentsstatic int flag = 0; // DFS Traversalstatic int DFS(List<int> []adj, int k, int i, int x){ // Initialise ans to 1 int ans = 1; // Traverse the adjacency // for vertex i foreach (int it in adj[i]) { if (it != k) { ans += DFS(adj, i, it, x); } } // If number of nodes is // greater than x, then // the tree cannot be split if (ans > x) { flag = 1; return 0; } // Check for requirement // of nodes else if (ans == x) { ans = 0; } return ans;} // A utility function to add// an edge in an undirected// Treestatic void addEdge(List<int> []adj, int u, int v){ adj[u].Add(v); adj[v].Add(u);} // Driver's Codepublic static void Main(String[] args){ int N = 15, K = 5; // Adjacency List List<int> []adj = new List<int>[N + 1]; for(int i= 0; i < N + 1; i++) adj[i] = new List<int>(); // Adding edges to List addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 2, 4); addEdge(adj, 4, 5); addEdge(adj, 5, 6); addEdge(adj, 5, 7); addEdge(adj, 4, 8); addEdge(adj, 4, 9); addEdge(adj, 8, 11); addEdge(adj, 10, 11); addEdge(adj, 11, 14); addEdge(adj, 9, 12); addEdge(adj, 12, 15); addEdge(adj, 12, 13); // Check if tree can be split // into K Connected Components // of equal number of nodes if (N % K == 0) { // DFS call to Check // if tree can be split DFS(adj, -1, 1, N / K); } // If flag is 0, then the // given can be split to // Connected Components Console.Write(flag==1 ? "NO" : "YES"); }}// This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to detect whether// the given Tree can be split// into K equals components// For checking if the graph// can be split into K equal// Connected Componentsvar flag = 0;// DFS Traversalfunction DFS(adj, k, i, x){ // Initialise ans to 1 var ans = 1; // Traverse the adjacency // for vertex i adj[i].forEach(element => { if (element != k) { ans += DFS(adj, i, element, x); } }); // If number of nodes is // greater than x, then // the tree cannot be split if (ans > x) { flag = 1; return 0; } // Check for requirement // of nodes else if (ans == x) { ans = 0; } return ans;}// A utility function to add// an edge in an undirected// Treefunction addEdge(adj, u, v){ adj[u].push(v); adj[v].push(u);}// Driver's Codevar N = 15, K = 5;// Adjacency Listvar adj = Array.from(Array(N+1), ()=> Array());// Adding edges to ListaddEdge(adj, 1, 2);addEdge(adj, 2, 3);addEdge(adj, 2, 4);addEdge(adj, 4, 5);addEdge(adj, 5, 6);addEdge(adj, 5, 7);addEdge(adj, 4, 8);addEdge(adj, 4, 9);addEdge(adj, 8, 11);addEdge(adj, 10, 11);addEdge(adj, 11, 14);addEdge(adj, 9, 12);addEdge(adj, 12, 15);addEdge(adj, 12, 13);// Check if tree can be split// into K Connected Components// of equal number of nodesif (N % K == 0) { // DFS call to Check // if tree can be split DFS(adj, -1, 1, N / K);}// If flag is 0, then the// given can be split to// Connected Componentsdocument.write(flag ? "NO" : "YES");</script> |
Output:
YES
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges
Auxiliary Space: O(V) due to recursion stack space. Ignoring the space used by the adjacency list as it is given.
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!
