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)