Create a Tree of numbers [1, N] following K triplets (A, B, C) such that any path from A to C cannot contain B
Given an integer N representing numbers [1, N] and K restrictions in the form of triplets {A, B, C}, such that any simple path from A to C cannot contain B. The task is to create a Tree of numbers [1, N] following these K restrictions and print the edges of that tree. Assume that the tree always exists for the given set of restrictions.
Examples:
Input: N = 8, restrictions[] = {{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {6, 7, 4}}
Output:
3 4
3 5
3 1
1 2
2 8
8 6
8 7
Explanation: The tree formed following the given restrictions is:3
/ | \
4 5 1
|
2
|
8
/ \
6 7Input: N = 8, restrictions[] = {{3, 2, 4}, {3, 5, 4}, {5, 8, 7}, {6, 1, 8}}
Output:
3 1
3 2
3 4
3 5
3 6
3 7
3 8
Approach: The basic catch in this problem is that for a tree each node can only have one parent. So, there’s always a node on which no restriction applies and it can lie between any two nodes. So, connect that node to all nodes to get the answer. Now to solve this problem follow the below steps:
- Create a boolean vector visited which will mark all node 1 with restrictions, and initialize it with 0.
- Iterate a loop for all restrictions and mark all nodes with 1 in the visited array that has restrictions.
- Store the value of node which have a 0 value in visited array as root.
- Connect all nodes with root.
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the tree following // the given restrictions void RestrictedTree( vector<vector< int > >& restrictions, int N) { // Vector to track the restricted nodes vector< int > visited(N + 1, false ); // Loop to mark the restricted node visited for ( int index = 0; index < restrictions.size(); index++) { int a = restrictions[index][1]; visited[a] = true ; } // Variable to consider root node int root = -1; for ( int index = 1; index <= N; index++) { if (visited[index] == false ) { root = index; break ; } } // Connecting all node to the root node for ( int index = 1; index <= N; index++) { if (index != root) { cout << root << " " << index << "\n" ; } } return ; } // Driver code int main() { int N = 8; vector<vector< int > > restrictions = { { 3, 2, 4 }, { 3, 5, 4 }, { 5, 8, 7 }, { 6, 1, 8 } }; RestrictedTree(restrictions, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to print the tree following // the given restrictions static void RestrictedTree( int [][]restrictions, int N) { // Vector to track the restricted nodes boolean visited[] = new boolean [N + 1 ]; // Loop to mark the restricted node visited for ( int index = 0 ; index < restrictions.length; index++) { int a = restrictions[index][ 1 ]; visited[a] = true ; } // Variable to consider root node int root = - 1 ; for ( int index = 1 ; index <= N; index++) { if (visited[index] == false ) { root = index; break ; } } // Connecting all node to the root node for ( int index = 1 ; index <= N; index++) { if (index != root) { System.out.print(root+ " " + index+ "\n" ); } } return ; } // Driver code public static void main(String[] args) { int N = 8 ; int [][]restrictions = { { 3 , 2 , 4 }, { 3 , 5 , 4 }, { 5 , 8 , 7 }, { 6 , 1 , 8 } }; RestrictedTree(restrictions, N); } } // This code is contributed by 29AjayKumar |
Python3
# Python Program to implement # the above approach # Function to print the tree following # the given restrictions def RestrictedTree(restrictions, N): # Vector to track the restricted nodes visited = [ False ] * (N + 1 ) # Loop to mark the restricted node visited for index in range ( len (restrictions)): a = restrictions[index][ 1 ] visited[a] = True # Variable to consider root node root = - 1 for index in range ( 1 , N + 1 ): if (visited[index] = = False ): root = index break # Connecting all node to the root node for index in range ( 1 , N + 1 ): if (index ! = root): print (f '{root} {index}' ) return # Driver code N = 8 restrictions = [ [ 3 , 2 , 4 ], [ 3 , 5 , 4 ], [ 5 , 8 , 7 ], [ 6 , 1 , 8 ] ] RestrictedTree(restrictions, N) # This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approach using System; class GFG { // Function to print the tree following // the given restrictions static void RestrictedTree( int [,]restrictions, int N) { // Vector to track the restricted nodes bool []visited = new bool [N + 1]; // Loop to mark the restricted node visited for ( int index = 0; index < restrictions.GetLength(0); index++) { int a = restrictions[index,1]; visited[a] = true ; } // Variable to consider root node int root = -1; for ( int index = 1; index <= N; index++) { if (visited[index] == false ) { root = index; break ; } } // Connecting all node to the root node for ( int index = 1; index <= N; index++) { if (index != root) { Console.Write(root+ " " + index+ "\n" ); } } return ; } // Driver code public static void Main( string [] args) { int N = 8; int [,]restrictions = { { 3, 2, 4 }, { 3, 5, 4 }, { 5, 8, 7 }, { 6, 1, 8 } }; RestrictedTree(restrictions, N); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to print the tree following // the given restrictions function RestrictedTree( restrictions, N) { // Vector to track the restricted nodes let visited = new Array(N + 1).fill( false ); // Loop to mark the restricted node visited for (let index = 0; index < restrictions.length; index++) { let a = restrictions[index][1]; visited[a] = true ; } // Variable to consider root node let root = -1; for (let index = 1; index <= N; index++) { if (visited[index] == false ) { root = index; break ; } } // Connecting all node to the root node for (let index = 1; index <= N; index++) { if (index != root) { document.write(root + " " + index + '<br>' ); } } return ; } // Driver code let N = 8; let restrictions = [ [3, 2, 4], [3, 5, 4], [5, 8, 7], [6, 1, 8] ]; RestrictedTree(restrictions, N); // This code is contributed by Potta Lokesh </script> |
3 1 3 2 3 4 3 5 3 6 3 7 3 8
Time Complexity: O(N)
Auxiliary Space: O(N)