Data Modelling & AI Data Structure & Algorithm

Test case generator for Tree using Disjoint-Set Union

23 June 2025

0

In this article, we will generate test cases such that given set edges form a Tree. Below are the two conditions of the Tree:

It should have one less edge than the number of vertices.
There should be no cycle in it.

Approach: The idea is to run a loop and add one edge each time that is generated randomly, and for adding each edge we will check whether it is forming cycle or not. We can ensure that cycle is present or not with the help of Disjoint-Set Union. If adding any edges form cycle then ignore the current edges and generate the new set of edges. Else print the edges with randomly generated weight. Below is the implementation of the above approach:

C++

// C++ implementation to generate
// test-case for the Tree
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
#define fast ios_base::sync_with_stdio(false);
#define MOD 1000000007
 
// Maximum Number Of Nodes
#define MAXNODE 10;
 
// Maximum Number Of testCases
#define MAXT 10;
 
// Maximum weight
#define MAXWEIGHT 100;
 
// Function for the path
// compression technique
ll find(ll parent[], ll x)
{
    // If parent found
    if (parent[x] == x)
        return x;
 
    // Find parent recursively
    parent[x] = find(parent, parent[x]);
 
    // Return the parent node of x
    return parent[x];
}
 
// Function to compute the union
// by rank
void merge(ll parent[], ll size[],
           ll x, ll y)
{
    ll r1 = find(parent, x);
    ll r2 = find(parent, y);
 
    if (size[r1] < size[r2]) {
        parent[r1] = r2;
        size[r2] += size[r1];
    }
    else {
        parent[r2] = r1;
        size[r1] += size[r2];
    }
}
 
// Function to generate the
// test-cases for the tree
void generate()
{
    ll t;
    t = 1 + rand() % MAXT;
 
    // Number of testcases
    cout << t << "\n";
    while (t--) {
 
        // for 2<=Number of Nodes<=MAXNODE
 
        // Randomly generate number of edges
        ll n = 2 + rand() % MAXNODE;
        ll i;
        cout << n << "\n";
        ll parent[n + 1];
        ll size[n + 1];
 
        // Initialise parent and
        // size arrays
        for (i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
 
        vector<pair<ll, ll> > Edges;
        vector<ll> weights;
 
        // Now We have add N-1 edges
        for (i = 1; i <= n - 1; i++) {
            ll x = 1 + rand() % n;
            ll y = 1 + rand() % n;
 
            // Find edges till it does not
            // forms a cycle
            while (find(parent, x)
                   == find(parent, y)) {
 
                x = 1 + rand() % n;
                y = 1 + rand() % n;
            }
 
            // Merge the nodes in tree
            merge(parent, size, x, y);
 
            // Store the current edge and weight
            Edges.push_back(make_pair(x, y));
            ll w = 1 + rand() % MAXWEIGHT;
            weights.push_back(w);
        }
 
        // Print the set of edges
        // with weight
        for (i = 0; i < Edges.size(); i++) {
 
            cout << Edges[i].first << " "
                 << Edges[i].second;
            cout << " " << weights[i];
            cout << "\n";
        }
    }
}
 
// Driver Code
int main()
{
    // Uncomment the below line to store
    // the test data in a file
    // freopen ("output.txt", "w", stdout);
 
    // For random values every time
    srand(time(NULL));
 
    fast;
 
    generate();
}

Java

import java.util.*;
 
public class TreeTestCases {
    // Maximum Number Of Nodes
    static final int MAXNODE = 10;
    // Maximum Number Of testCases
    static final int MAXT = 10;
    // Maximum weight
    static final int MAXWEIGHT = 100;
 
    // Function for the path compression technique
    static int find(int[] parent, int x) {
        // If parent found
        if (parent[x] == x) {
            return x;
        }
        // Find parent recursively
        parent[x] = find(parent, parent[x]);
        // Return the parent node of x
        return parent[x];
    }
 
    // Function to compute the union by rank
    static void merge(int[] parent, int[] size, int x, int y) {
        int r1 = find(parent, x);
        int r2 = find(parent, y);
        if (size[r1] < size[r2]) {
            parent[r1] = r2;
            size[r2] += size[r1];
        } else {
            parent[r2] = r1;
            size[r1] += size[r2];
        }
    }
 
    // Function to generate the test-cases for the tree
    static void generate() {
        Random rand = new Random();
        // Number of testcases
        int t = rand.nextInt(MAXT) + 1;
        System.out.println(t);
        for (int i = 0; i < t; i++) {
            // for 2<=Number of Nodes<=MAXNODE
            // Randomly generate number of edges
            int n = rand.nextInt(MAXNODE - 1) + 2;
            System.out.println(n);
            int[] parent = new int[n + 1];
            int[] size = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                parent[j] = j;
                size[j] = 1;
            }
            List<int[]> edges = new ArrayList<>();
            List<Integer> weights = new ArrayList<>();
            // Now We have to add N-1 edges
            for (int j = 0; j < n - 1; j++) {
                int x = rand.nextInt(n) + 1;
                int y = rand.nextInt(n) + 1;
                // Find edges till it does not forms a cycle
                while (find(parent, x) == find(parent, y)) {
                    x = rand.nextInt(n) + 1;
                    y = rand.nextInt(n) + 1;
                }
                // Merge the nodes in tree
                merge(parent, size, x, y);
                // Store the current edge and weight
                edges.add(new int[] {x, y});
                int w = rand.nextInt(MAXWEIGHT) + 1;
                weights.add(w);
            }
            // Print the set of edges with weight
            for (int j = 0; j < edges.size(); j++) {
                int[] edge = edges.get(j);
                System.out.println(edge[0] + " " + edge[1] + " " + weights.get(j));
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args) {
        // For random values every time
        Random rand = new Random();
        rand.setSeed(System.currentTimeMillis());
        generate();
    }
}

Python3

# Python3 implementation to generate
# test-case for the Tree
import random
 
# Maximum Number Of Nodes
MAXNODE = 10
 
# Maximum Number Of testCases
MAXT = 10
 
# Maximum weight
MAXWEIGHT = 100
 
# Function for the path
# compression technique
def find(parent, x):
   
    # If parent found
    if parent[x] == x:
        return x
       
    # Find parent recursively
    parent[x] = find(parent, parent[x])
     
    # Return the parent node of x
    return parent[x]
 
# Function to compute the union
# by rank
def merge(parent, size, x, y):
    r1 = find(parent, x)
    r2 = find(parent, y)
 
    if size[r1] < size[r2]:
        parent[r1] = r2
        size[r2] += size[r1]
    else:
        parent[r2] = r1
        size[r1] += size[r2]
 
# Function to generate the
# test-cases for the tree
def generate():
   
    # Number of testcases
    t = random.randint(1, MAXT)
    print(t)
    for _ in range(t):
        # for 2<=Number of Nodes<=MAXNODE
 
        # Randomly generate number of edges
        n = random.randint(2, MAXNODE)
        print(n)
        parent = [i for i in range(n + 1)]
        size = [1 for _ in range(n + 1)]
        Edges = []
        weights = []
 
        # Now We have add N-1 edges
        for i in range(n - 1):
            x = random.randint(1, n)
            y = random.randint(1, n)
 
            # Find edges till it does not
            # forms a cycle
            while find(parent, x) == find(parent, y):
                x = random.randint(1, n)
                y = random.randint(1, n)
 
            # Merge the nodes in tree
            merge(parent, size, x, y)
 
            # Store the current edge and weight
            Edges.append((x, y))
            w = random.randint(1, MAXWEIGHT)
            weights.append(w)
 
        # Print the set of edges
        # with weight
        for i in range(len(Edges)):
            print(Edges[i][0], Edges[i][1], weights[i])
 
# Driver Code
if __name__ == "__main__":
   
    # Uncomment the below line to store
    # the test data in a file
    # open("output.txt", "w").close()
    # open("output.txt", "w").write(generate())
 
    # For random values every time
    random.seed(None)
 
    generate()
     
# This code is contributed by Potta Lokesh

C#

// C# implementation to generate
// test-case for the Tree
 
using System;
using System.Collections.Generic;
 
class GFG {
    static int MAXNODE = 10;
    static int MAXT = 10;
    static int MAXWEIGHT = 100;
    static int[] parent = new int[MAXNODE + 1];
    static int[] size = new int[MAXNODE + 1];
 
    // Function for the path
    // compression technique
    static int find(int[] parent, int x)
    {
        // If parent found
        if (parent[x] == x)
            return x;
 
        // Find parent recursively
        parent[x] = find(parent, parent[x]);
 
        // Return the parent node of x
        return parent[x];
    }
 
    // Function to compute the union
    // by rank
    static void merge(int[] parent, int[] size, int x,
                      int y)
    {
        int r1 = find(parent, x);
        int r2 = find(parent, y);
 
        if (size[r1] < size[r2]) {
            parent[r1] = r2;
            size[r2] += size[r1];
        }
        else {
            parent[r2] = r1;
            size[r1] += size[r2];
        }
    }
 
    // Function to generate the
    // test-cases for the tree
    static void generate()
    {
        Random rand = new Random();
 
        int t = 1 + rand.Next() % MAXT;
 
        // Number of testcases
        Console.WriteLine(t);
        while (t-- > 0) {
 
            // for 2<=Number of Nodes<=MAXNODE
 
            // Randomly generate number of edges
            int n = 2 + rand.Next() % MAXNODE;
            int i;
            Console.WriteLine(n);
 
            // Initialise parent and
            // size arrays
            for (i = 1; i <= n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
 
            List<Tuple<int, int> > Edges
                = new List<Tuple<int, int> >();
            List<int> weights = new List<int>();
 
            // Now We have add N-1 edges
            for (i = 1; i <= n - 1; i++) {
                int x = 1 + rand.Next() % n;
                int y = 1 + rand.Next() % n;
 
                // Find edges till it does not
                // forms a cycle
                while (find(parent, x) == find(parent, y)) {
 
                    x = 1 + rand.Next() % n;
                    y = 1 + rand.Next() % n;
                }
 
                // Merge the nodes in tree
                merge(parent, size, x, y);
 
                // Store the current edge and weight
                Edges.Add(new Tuple<int, int>(x, y));
                int w = 1 + rand.Next() % MAXWEIGHT;
                weights.Add(w);
            }
 
            // Print the set of edges
            // with weight
            for (i = 0; i < Edges.Count; i++) {
                Console.WriteLine(Edges[i].Item1 + " "
                                  + Edges[i].Item2 + " "
                                  + weights[i]);
            }
        }
    }
 
    // Driver Code
    static void Main()
    {
        // Uncomment the below line to store
        // the test data in a file
        // System.setOut(new PrintStream(new
        // File("output.txt")));
 
        // For random values every time
        Random rand = new Random();
 
        generate();
    }
}

Javascript

// JavaScript implementation to generate
// test-case for the Tree
 
const MAXNODE = 10;
const MAXT = 10;
const MAXWEIGHT = 100;
const parent = new Array(MAXNODE + 1);
const size = new Array(MAXNODE + 1);
 
// Function for the path
// compression technique
function find(parent, x) {
  // If parent found
  if (parent[x] == x)
    return x;
 
  // Find parent recursively
  parent[x] = find(parent, parent[x]);
 
  // Return the parent node of x
  return parent[x];
}
 
// Function to compute the union
// by rank
function merge(parent, size, x, y) {
  let r1 = find(parent, x);
  let r2 = find(parent, y);
 
  if (size[r1] < size[r2]) {
    parent[r1] = r2;
    size[r2] += size[r1];
  } else {
    parent[r2] = r1;
    size[r1] += size[r2];
  }
}
 
// Function to generate the
// test-cases for the tree
function generate() {
   
 
  let t = 1 + Math.floor(Math.random() * MAXT);
 
  // Number of testcases
  console.log(t);
  while (t-- > 0) {
    // for 2<=Number of Nodes<=MAXNODE
 
    // Randomly generate number of edges
    let n = 2 + Math.floor(Math.random() * MAXNODE);
    let i;
    console.log(n);
 
    // Initialise parent and
    // size arrays
    for (i = 1; i <= n; i++) {
      parent[i] = i;
      size[i] = 1;
    }
 
    const Edges = [];
    const weights = [];
 
    // Now We have add N-1 edges
    for (i = 1; i <= n - 1; i++) {
      let x = 1 + Math.floor(Math.random() * n);
      let y = 1 + Math.floor(Math.random() * n);
 
      // Find edges till it does not
      // forms a cycle
      while (find(parent, x) == find(parent, y)) {
        x = 1 + Math.floor(Math.random() * n);
        y = 1 + Math.floor(Math.random() * n);
      }
 
      // Merge the nodes in tree
      merge(parent, size, x, y);
 
      // Store the current edge and weight
      Edges.push([x, y]);
      let w = 1 + Math.floor(Math.random() * MAXWEIGHT);
      weights.push(w);
    }
 
    // Print the set of edges
    // with weight
    for (i = 0; i < Edges.length; i++) {
      console.log(`${Edges[i][0]} ${Edges[i][1]} ${weights[i]}`);
    }
  }
}
 
// Driver Code
generate();

Output:

Time Complexity: O(N*logN)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Test case generator for Tree using Disjoint-Set Union

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

Forget Bluetooth — this Android feature makes sharing files to a Mac ridiculously easy

EDITOR PICKS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR POSTS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR CATEGORY

ABOUT US

FOLLOW US