Cada casa en la colonia tiene como máximo una tubería que entra y como máximo una tubería que sale. Los tanques y grifos deben instalarse de tal manera que cada casa con una tubería de salida pero sin tubería de entrada tenga un tanque instalado en su techo y cada casa con solo una tubería de entrada y sin tubería de salida tenga un grifo.
Dados dos números enteros n y p que denotan el número de casas y el número de tuberías. Las conexiones de tubería entre las casas contienen tres valores de entrada: a_i , b_i , d_i que denota la tubería de diámetro d_i desde la casa a_i hasta la casa b_i , encuentre la solución eficiente para la red.
La salida contendrá el número de pares de tanques y grifos t instalados en primera línea y las siguientes t líneas contienen tres números enteros: número de casa del tanque, número de casa del grifo y el diámetro mínimo de tubería entre ellos.
Ejemplos:
Entrada: 4 2
1 2 60
3 4 50
Salida: 2
1 2 60
3 4 50
Explicación:
Los componentes conectados son: 1->2 y 3->4
Por lo tanto, nuestra respuesta es 2 seguido de 1 2 60 y 3 4 50.Entrada: 9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66
Salida: 3
2 8 22
3 1 66
5 6 10
Explicación:
Los componentes conectados son 3->1, 5->9-> 7->4->6 y 2->8 .
Por lo tanto, nuestra respuesta es 3 seguido de 2 8 22, 3 1 66, 5 6 10
Acercarse:
- Realice DFS de casas apropiadas para encontrar todos los diferentes componentes conectados. El número de diferentes componentes conectados es nuestra respuesta t.
- Las siguientes t líneas de la salida son el comienzo del componente conectado, el final del componente conectado y el diámetro mínimo desde el comienzo hasta el final del componente conectado en cada línea.
- Dado que los tanques se pueden instalar solo en las casas que tienen tubería de salida y ninguna tubería de entrada, por lo tanto, estas son casas apropiadas para iniciar DFS desde, es decir, realizar DFS desde tales casas no visitadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find efficient
// solution for the network
#include <cstring> // For memset
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::memset;
using std::vector;
// number of houses and number
// of pipes
int number_of_houses, number_of_pipes;
// Array rd stores the
// ending vertex of pipe
int ending_vertex_of_pipes[1100];
// Array wd stores the value
// of diameters between two pipes
int diameter_between_two_pipes[1100];
// Array cd stores the
// starting end of pipe
int starting_vertex_of_pipes[1100];
// Vector a, b, c are used
// to store the final output
vector<int> a;
vector<int> b;
vector<int> c;
int ans;
int dfs(int w)
{
if (starting_vertex_of_pipes[w] == 0)
return w;
if (diameter_between_two_pipes[w] < ans)
ans = diameter_between_two_pipes[w];
return dfs(starting_vertex_of_pipes[w]);
}
// Function performing calculations.
void solve(int arr[][3])
{
for (int i = 0; i < number_of_pipes; ++i) {
int house_1 = arr[i][0], house_2 = arr[i][1],
pipe_diameter = arr[i][2];
starting_vertex_of_pipes[house_1] = house_2;
diameter_between_two_pipes[house_1] = pipe_diameter;
ending_vertex_of_pipes[house_2] = house_1;
}
a.clear();
b.clear();
c.clear();
for (int j = 1; j <= number_of_houses; ++j)
/*If a pipe has no ending vertex
but has starting vertex i.e is
an outgoing pipe then we need
to start DFS with this vertex.*/
if (ending_vertex_of_pipes[j] == 0
&& starting_vertex_of_pipes[j]) {
ans = 1000000000;
int w = dfs(j);
// We put the details of component
// in final output array
a.push_back(j);
b.push_back(w);
c.push_back(ans);
}
cout << a.size() << endl;
for (int j = 0; j < a.size(); ++j)
cout << a[j] << " " << b[j] << " " << c[j] << endl;
}
// driver function
int main()
{
number_of_houses = 9, number_of_pipes = 6;
memset(ending_vertex_of_pipes, 0,
sizeof(ending_vertex_of_pipes));
memset(starting_vertex_of_pipes, 0,
sizeof(starting_vertex_of_pipes));
memset(diameter_between_two_pipes, 0,
sizeof(diameter_between_two_pipes));
int arr[][3]
= { { 7, 4, 98 }, { 5, 9, 72 }, { 4, 6, 10 },
{ 2, 8, 22 }, { 9, 7, 17 }, { 3, 1, 66 } };
solve(arr);
return 0;
}
Java
// Java program to find efficient
// solution for the network
import java.util.*;
class GFG {
// number of houses and number
// of pipes
static int number_of_houses, number_of_pipes;
// Array rd stores the
// ending vertex of pipe
static int ending_vertex_of_pipes[] = new int[1100];
// Array wd stores the value
// of diameters between two pipes
static int diameter_of_pipes[] = new int[1100];
// Array cd stores the
// starting end of pipe
static int starting_vertex_of_pipes[] = new int[1100];
// arraylist a, b, c are used
// to store the final output
static List<Integer> a = new ArrayList<Integer>();
static List<Integer> b = new ArrayList<Integer>();
static List<Integer> c = new ArrayList<Integer>();
static int ans;
static int dfs(int w)
{
if (starting_vertex_of_pipes[w] == 0)
return w;
if (diameter_of_pipes[w] < ans)
ans = diameter_of_pipes[w];
return dfs(starting_vertex_of_pipes[w]);
}
// Function to perform calculations.
static void solve(int arr[][])
{
int i = 0;
while (i < number_of_pipes) {
int q = arr[i][0];
int h = arr[i][1];
int t = arr[i][2];
starting_vertex_of_pipes[q] = h;
diameter_of_pipes[q] = t;
ending_vertex_of_pipes[h] = q;
i++;
}
a = new ArrayList<Integer>();
b = new ArrayList<Integer>();
c = new ArrayList<Integer>();
for (int j = 1; j <= number_of_houses; ++j)
/*If a pipe has no ending vertex
but has starting vertex i.e is
an outgoing pipe then we need
to start DFS with this vertex.*/
if (ending_vertex_of_pipes[j] == 0
&& starting_vertex_of_pipes[j] > 0) {
ans = 1000000000;
int w = dfs(j);
// We put the details of
// component in final output
// array
a.add(j);
b.add(w);
c.add(ans);
}
System.out.println(a.size());
for (int j = 0; j < a.size(); ++j)
System.out.println(a.get(j) + " " + b.get(j)
+ " " + c.get(j));
}
// main function
public static void main(String args[])
{
number_of_houses = 9;
number_of_pipes = 6;
// set the value of the array
// to zero
for (int i = 0; i < 1100; i++)
ending_vertex_of_pipes[i]
= starting_vertex_of_pipes[i]
= diameter_of_pipes[i] = 0;
int arr[][]
= { { 7, 4, 98 }, { 5, 9, 72 }, { 4, 6, 10 },
{ 2, 8, 22 }, { 9, 7, 17 }, { 3, 1, 66 } };
solve(arr);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find efficient # solution for the network # number of houses and number # of pipes n = 0 p = 0 # Array rd stores the # ending vertex of pipe rd = [0]*1100 # Array wd stores the value # of diameters between two pipes wt = [0]*1100 # Array cd stores the # starting end of pipe cd = [0]*1100 # List a, b, c are used # to store the final output a = [] b = [] c = [] ans = 0 def dfs(w): global ans if (cd[w] == 0): return w if (wt[w] < ans): ans = wt[w] return dfs(cd[w]) # Function performing calculations. def solve(arr): global ans i = 0 while (i < p): q = arr[i][0] h = arr[i][1] t = arr[i][2] cd[q] = h wt[q] = t rd[h] = q i += 1 a = [] b = [] c = [] '''If a pipe has no ending vertex but has starting vertex i.e is an outgoing pipe then we need to start DFS with this vertex.''' for j in range(1, n + 1): if (rd[j] == 0 and cd[j]): ans = 1000000000 w = dfs(j) # We put the details of component # in final output array a.append(j) b.append(w) c.append(ans) print(len(a)) for j in range(len(a)): print(a[j], b[j], c[j]) # Driver function n = 9 p = 6 arr = [[7, 4, 98], [5, 9, 72], [4, 6, 10 ], [2, 8, 22 ], [9, 7, 17], [3, 1, 66]] solve(arr) # This code is contributed by shubhamsingh10
C#
// C# program to find efficient
// solution for the network
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// number of houses and number
// of pipes
static int n, p;
// Array rd stores the
// ending vertex of pipe
static int []rd = new int[1100];
// Array wd stores the value
// of diameters between two pipes
static int []wt = new int[1100];
// Array cd stores the
// starting end of pipe
static int []cd = new int[1100];
// arraylist a, b, c are used
// to store the final output
static List <int> a =
new List <int>();
static List <int> b =
new List <int>();
static List <int> c =
new List <int>();
static int ans;
static int dfs(int w)
{
if (cd[w] == 0)
return w;
if (wt[w] < ans)
ans = wt[w];
return dfs(cd[w]);
}
// Function to perform calculations.
static void solve(int [,]arr)
{
int i = 0;
while (i < p)
{
int q = arr[i,0];
int h = arr[i,1];
int t = arr[i,2];
cd[q] = h;
wt[q] = t;
rd[h] = q;
i++;
}
a = new List <int>();
b = new List <int>();
c = new List <int>();
for (int j = 1; j <= n; ++j)
/*If a pipe has no ending vertex
but has starting vertex i.e is
an outgoing pipe then we need
to start DFS with this vertex.*/
if (rd[j] == 0 && cd[j] > 0)
{
ans = 1000000000;
int w = dfs(j);
// We put the details of
// component in final output
// array
a.Add(j);
b.Add(w);
c.Add(ans);
}
Console.WriteLine(a.Count);
for (int j = 0; j < a.Count; ++j)
Console.WriteLine(a[j] + " "
+ b[j] + " " + c[j]);
}
// Driver code
public static void Main(String []args)
{
n = 9;
p = 6;
// set the value of the array
// to zero
for(int i = 0; i < 1100; i++)
rd[i] = cd[i] = wt[i] = 0;
int [,]arr = { { 7, 4, 98 },
{ 5, 9, 72 },
{ 4, 6, 10 },
{ 2, 8, 22 },
{ 9, 7, 17 },
{ 3, 1, 66 } };
solve(arr);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find efficient
// solution for the network
// number of houses and number
// of pipes
let n, p;
// Array rd stores the
// ending vertex of pipe
let rd=new Array(1100);
// Array wd stores the value
// of diameters between two pipes
let wt=new Array(1100);
// Array cd stores the
// starting end of pipe
let cd=new Array(1100);
// arraylist a, b, c are used
// to store the final output
let a=[];
let b=[];
let c=[];
let ans;
function dfs(w)
{
if (cd[w] == 0)
return w;
if (wt[w] < ans)
ans = wt[w];
return dfs(cd[w]);
}
// Function to perform calculations.
function solve(arr)
{
let i = 0;
while (i < p)
{
let q = arr[i][0];
let h = arr[i][1];
let t = arr[i][2];
cd[q] = h;
wt[q] = t;
rd[h] = q;
i++;
}
a=[];
b=[];
c=[];
for (let j = 1; j <= n; ++j)
/*If a pipe has no ending vertex
but has starting vertex i.e is
an outgoing pipe then we need
to start DFS with this vertex.*/
if (rd[j] == 0 && cd[j]>0) {
ans = 1000000000;
let w = dfs(j);
// We put the details of
// component in final output
// array
a.push(j);
b.push(w);
c.push(ans);
}
document.write(a.length+"<br>");
for (let j = 0; j < a.length; ++j)
document.write(a[j] + " "
+ b[j] + " " + c[j]+"<br>");
}
// main function
n = 9;
p = 6;
// set the value of the array
// to zero
for(let i = 0; i < 1100; i++)
rd[i] = cd[i] = wt[i] = 0;
let arr = [[ 7, 4, 98 ],
[ 5, 9, 72 ],
[ 4, 6, 10 ],
[ 2, 8, 22 ],
[ 9, 7, 17 ],
[ 3, 1, 66 ]];
solve(arr);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
3 2 8 22 3 1 66 5 6 10