Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Sample Examples
2.
Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Frequently asked questions
3.1.
What is a graph?
3.2.
What is dfs?
3.3.
Can there be multiple shortest paths in a graph?
4.
Conclusion
Last Updated: Mar 27, 2024

Water Connection Problem

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

According to the water connection problem, each home in the colony has a maximum of one pipe entering it and a maximum of one pipe exiting it. Every property with one outgoing pipe but no incoming pipe is to have a tank built on its roof, and every house with just an incoming pipe but no departing pipe is to have a tap installed.

As a result, we are given the two integers n and p, which stand for the quantity of pipes and dwellings respectively. The pipe connections between the houses have three input values: ai, bi, and di, which represent the diameter di of the pipe connecting ai to bi ;Where i belongs to 0 < i ≤ n we have to find an efficient solution for the network. 

The output contains the number of pair of tanks and taps, the subsequent lines will contain 3 integers where the 1st integer represents the home containing the tank, 2nd integer represents the home having the tap and the 3rd integer denoting the minimum diameter of the pipe between them.

So before we deep dive into the solution to this problem, we should first look at some examples to understand the problem better.

Sample Examples

Input:    

4 2
1 3 55
2 4 45

 

Output: 

2
1 3 55
2 4 45

Explanation:

Connected components are: 
1->3 and 2->4
Therefore, the answer is 2 followed by
1 3 55 and 2 4 45.

 

Input:    

9 6
1 2 33
2 3 45
4 5 10
5 8 22
7 6 17
3 7 66

 

Output: 

2
1 6 17
4 8 10

Explanation:

Connected components are: 
1->2->3->7->6 and 4->5->8
Therefore, the answer is 2 followed by
1 6 17 and 4 8 10.

Approach

So the approach of this water connection problem is to perform DFS from houses to find all different connected components. The other connected components will be stored in a variable named x

So the following x lines of the output will be the first connected house followed by the last connected house. We will perform DFS on unvisited houses.

DFS Algorithm should be used from the relevant homes to locate all associated components. Our response to t is the number of various connected components. The linked component's start, end, and the smallest diameter between the connected component's start and finish are shown on the next t lines of the output for each line. Since tanks can only be built on homes with outgoing pipes but no incoming pipes, these are the best homes from which to do DFS, or start it from such unvisited homes.

Implementation in C++

// C++ code for Water Connection Problem
#include <bits/stdc++.h>
using namespace std;

int ans;
void printSolution(vector<int> &st, vector<int> &en, vector<int> &dm)
{
    cout << st.size() << endl;
    for (int j = 0; j < st.size(); ++j)
        cout << st[j] << " " << en[j]
             << " " << dm[j] << endl;
}
int dfs(int w, vector<int> &diameter, vector<int> &start)
{
    if (start[w] == 0)
        return w;
    if (diameter[w] < ans)
        ans = diameter[w];
    return dfs(start[w], diameter, start);
}

// function for water connection problem
void water_connection(int arr[][3], int n, int pipes)
{
    // to store the starting vertex of the pipe
    vector<int> start(1100, 0);
    // to store the ending vertex of the pipe
    vector<int> ed(1100, 0);
    // to store the diameter of pipe
    vector<int> diameter(1100);
    int i = 0;

    for (i = 0; i < pipes; i++)
    {
        start[arr[i][0]] = arr[i][1];
        diameter[arr[i][0]] = arr[i][2];
        ed[arr[i][1]] = arr[i][0];
    }
    // st---> to store the starting vertex
    // en--> to store the ending vertex
    //  dm-->to store the minimum diameter of the pipe
    vector<int> st, en, dm;
    for (int j = 1; j <= n; ++j)

        // If there is a pipe that has no ending vertex but has
        // starting vertex then we will start DFS with this vertex
        if (ed[j] == 0)
        {
            if (start[j])
            {
                ans = INT_MAX;
                int w = dfs(j, diameter, start);

                // we will store the details of components in these final arrays
                st.push_back(j);
                en.push_back(w);
                dm.push_back(ans);
            }
        }
    printSolution(st, en, dm);
}

// driver function
int main()
{
    // to store the no of houses and pipes
    int n = 9, pipes = 6;
    int arr[][3] = {{2, 3, 45},
                    {4, 5, 10},
                    {5, 8, 22},
                    {1, 2, 33},
                    {7, 6, 17},
                    {3, 7, 66}};

    water_connection(arr, n, pipes);
    return 0;
}

 

Output:

2
1 6 17
4 8 10

Complexity Analysis

Time Complexity - O(N)

The time complexity of the above approach is O(N) because we have visited every node once.

Space Complexity - O(N)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently asked questions

What is a graph?

A graph is a non-linear data structure consisting of nodes and edges. The nodes can be called vertices, and edges connect two nodes.

What is dfs?

Dfs or depth-first search is an algorithm for traversing a graph.

Can there be multiple shortest paths in a graph?

Yes, we can find multiple shortest paths in a Graph.

Conclusion

In this article, we discussed the water connection problem and its most efficient approach. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Waterflow Problem
Next article
Construct a graph from the given degrees of all vertices
Live masterclass