Given a Directed Tree consisting of N nodes, the task is to check if there exists a node in the given tree such that all other nodes are reachable by removing any directed edge from the Tree and adding another directed edge between any pair of nodes in the Tree at most floor(N/2) times. If there exists any such node, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 3
Output: Yes
Explanation:
Remove the edge 2 -> 3 and insert an edge 1 -> 3.
Therefore, both the remaining nodes (2, 3) are now accessible from the node 1.
Count of operations required is 1, which is <= floor(3/2) (= 1).
Input: N = 5
Output: No
Approach: The idea to solve this problem is based on the following observations:
- Every node should have at least one parent node, i.e. every node should have at least 1 indegree to make the tree accessible from the required node.
- It can be concluded that if every node has at least 1 indegree, then all other nodes can be accessed.
- Therefore, the task is reduced to finding the number of nodes having 0 in-degrees and checking if it is at most N / 2 or not.
Follow the steps below to solve the problem:
- Store the in-degree of every node in the tree in an auxiliary array A[] of size (N + 1).
- Initialize this array as A[key] = pair for all (key-value) pairs in the Map.
- Initialize a variable, say count as 0, to store the number of nodes having in-degree equal to 0.
- Traverse the array A[] and count the number of array elements with value 0 and store it in the variable count.
- After completing the above steps, if the value of count is at most floor(N/2), then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;void findNode(map<int, int> mp, int n){ // Store the indegree // of every node int a[n]; for(int i = 0; i < n; i++) { a[i] = mp[i + 1]; } // Store the nodes having // indegree equal to 0 int count0 = 0; // Traverse the array for(int i = 0; i < n; i++) { // If the indegree // of i-th node is 0 if (a[i] == 0) { // Increment count0 by 1 count0++; } } count0 -= 1; // If the number of operations // needed is at most floor(n/2) if (count0 <= floor(((double)n) / ((double)2))) { cout << "Yes"; } // Otherwise else cout << "No";}// Driver Codeint main(){ // Given number of nodes int N = 3; // Given Directed Tree map<int, int> mp; mp[1] = 0; mp[2] = 2; mp[3] = 0; findNode(mp, N);}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.io.*;import java.util.HashMap;class GFG { // Function to check if there is a // node in tree from where all other // nodes are accessible or not public static void findNode(HashMap<Integer, Integer> map, int n) { // Store the indegree // of every node int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = map.getOrDefault(i + 1, 0); } // Store the nodes having // indegree equal to 0 int count0 = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the indegree // of i-th node is 0 if (a[i] == 0) { // Increment count0 by 1 count0++; } } count0 -= 1; // If the number of operations // needed is at most floor(n/2) if (count0 <= Math.floor(((double)n) / ((double)2))) { System.out.println("Yes"); } // Otherwise else System.out.println("No "); } // Driver Code public static void main(String[] args) { // Given number of nodes int N = 3; // Given Directed Tree HashMap<Integer, Integer> map = new HashMap<>(); map.put(1, 0); map.put(2, 2); map.put(3, 0); findNode(map, N); }} |
Python3
# python 3 program for the above approachdef findNode(mp, n): # Store the indegree # of every node a = [0]*n for i in range(n): a[i] = mp[i + 1] # Store the nodes having # indegree equal to 0 count0 = 0 # Traverse the array for i in range(n): # If the indegree # of i-th node is 0 if (a[i] == 0): # Increment count0 by 1 count0 += 1 count0 -= 1 # If the number of operations # needed is at most floor(n/2) if (count0 <= (n) / (2)): print("Yes") # Otherwise else: print("No")# Driver Codeif __name__ == "__main__": # Given number of nodes N = 3 # Given Directed Tree mp = {} mp[1] = 0 mp[2] = 2 mp[3] = 0 findNode(mp, N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to check if there is a // node in tree from where all other // nodes are accessible or not public static void findNode(Dictionary<int, int> map, int n) { // Store the indegree // of every node int[] a = new int[n]; for (int i = 0; i < n; i++) { if(map.ContainsKey(i+1)) a[i] = map[i + 1]; else a[i] = 0; } // Store the nodes having // indegree equal to 0 int count0 = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the indegree // of i-th node is 0 if (a[i] == 0) { // Increment count0 by 1 count0++; } } count0 -= 1; // If the number of operations // needed is at most floor(n/2) if (count0 <= Math.Floor(((double)n) / ((double)2))) { Console.WriteLine("Yes"); } // Otherwise else Console.WriteLine("No "); } static public void Main () { // Given number of nodes int N = 3; // Given Directed Tree Dictionary<int, int> map = new Dictionary<int, int>(); map[1]= 0; map[2] = 2; map[3] = 0; findNode(map, N); }}// This code is contributed by offbeat |
Javascript
<script>// Javascript program for the above approachfunction findNode(mp, n){ // Store the indegree // of every node var a = new Array(n); var i; for(i = 0; i < n; i++) { a[i] = mp[i + 1]; } // Store the nodes having // indegree equal to 0 var count0 = 0; // Traverse the array for(i = 0; i < n; i++) { // If the indegree // of i-th node is 0 if (a[i] == 0) { // Increment count0 by 1 count0++; } } count0 -= 1; // If the number of operations // needed is at most floor(n/2) if (count0 <= parseInt(n/2)) { document.write("Yes"); } // Otherwise else document.write("No");}// Driver Code // Given number of nodes var N = 3; // Given Directed Tree var mp = new Map(); mp.set(1,0); mp.set(2,2); mp.set(3,0); mp[1] = 0; mp[2] = 2; mp[3] = 0; findNode(mp, N);</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
