Dadas N ciudades que están conectadas mediante carreteras N-1 . Entre Ciudades [i, i+1] , existe una arista para todo i de 1 a N-1.
La tarea es establecer una conexión para el suministro de agua. Establezca el suministro de agua en una ciudad y el agua se transporta desde allí a otras ciudades mediante el transporte por carretera. Ciertas ciudades están bloqueadas, lo que significa que el agua no puede pasar por esa ciudad en particular. Determinar el número máximo de ciudades a las que se puede suministrar agua.
Formato de entrada:
- La primera línea contiene un número entero >fuerte>N que indica el número de ciudades.
- Las siguientes líneas N-1 contienen dos números enteros separados por espacios uv que denotan un camino entre la
ciudad u y v. - La siguiente línea contiene N enteros separados por espacios donde es 1 si la i-ésima ciudad está
bloqueada, de lo contrario es 0.
Ejemplos:
Entrada:
4
1 2
2 3
3 4
0 1 1 0
Salida:
2
Explicación: si se elige la ciudad 1, el agua se suministra de la
ciudad 1 a la 2. Si se elige la ciudad 4, el agua se suministra de la ciudad 4 a la 3
, por lo tanto, el máximo de 2 ciudades se pueden abastecer de agua.
Entrada:
7
1 2
2 3
3 4
4 5
5 6
6 7
0 1 1 0 0 0 0
Salida:
5
Explicación: Si se elige la ciudad 1, el agua se suministra de la
ciudad 1 a la 2 o si se elige la ciudad 4, se suministra el agua de la ciudad 4 a la
3, 5, 6 y 7, por lo tanto, un máximo de 5 ciudades se abastecen de agua.
Enfoque:
en esta publicación, se analiza una solución basada en BFS .
Realizamos una búsqueda en amplitud en cada ciudad y verificamos dos cosas: la ciudad no está bloqueada y la ciudad no es visitada. Si ambas condiciones se vuelven verdaderas, realizamos una búsqueda en amplitud desde esa ciudad y contamos el número de ciudades hasta las que se puede suministrar agua.
Esta solución también se puede lograr mediante una búsqueda en profundidad.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to solve water
// supply problem using BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to perform BFS
int bfsUtil(int v[], bool vis[], vector<int> adj[],
int src)
{
// Mark current source visited
vis[src] = true;
queue<int> q; //Queue for BFS
q.push(src); // Push src to queue
int count = 0;
while (!q.empty()) {
int p = q.front();
for (int i = 0; i < adj[p].size(); i++) {
// When the adjacent city not visited and
// not blocked, push city in the queue.
if (!vis[adj[p][i]] && v[adj[p][i]] == 0) {
count++;
vis[adj[p][i]] = true;
q.push(adj[p][i]);
}
// when the adjacent city is not visited
// but blocked so the blocked city is
// not pushed in queue
else if (!vis[adj[p][i]] && v[adj[p][i]] == 1) {
count++;
}
}
q.pop();
}
return count + 1;
}
// Utility function to perform BFS
int bfs(int N, int v[], vector<int> adj[])
{
bool vis[N + 1];
int max = 1, res;
// marking visited array false
for (int i = 1; i <= N; i++)
vis[i] = false;
// Check for each and every city
for (int i = 1; i <= N; i++) {
// Checks that city is not blocked
// and not visited.
if (v[i] == 0 && !vis[i]) {
res = bfsUtil(v, vis, adj, i);
if (res > max) {
max = res;
}
}
}
return max;
}
// Driver Code
int main()
{
int N = 4; // Denotes the number of cities
vector<int> adj[N + 1];
int v[N + 1];
// Adjacency list denoting road
// between city u and v
adj[1].push_back(2);
adj[2].push_back(1);
adj[2].push_back(3);
adj[3].push_back(2);
adj[3].push_back(4);
adj[4].push_back(3);
// array for storing whether ith
// city is blocked or not
v[1] = 0;
v[2] = 1;
v[3] = 1;
v[4] = 0;
cout<<bfs(N, v, adj);
return 0;
}
Java
// Java program to solve water
// supply problem using BFS
import java.util.*;
class GFG{
// Function to perform BFS
static int bfsUtil(int v[], boolean vis[],
Vector<Integer> adj[],
int src)
{
// Mark current source visited
vis[src] = true;
// Queue for BFS
Queue<Integer> q = new LinkedList<>();
// Push src to queue
q.add(src);
int count = 0;
while (!q.isEmpty())
{
int p = q.peek();
for(int i = 0; i < adj[p].size(); i++)
{
// When the adjacent city not
// visited and not blocked, push
// city in the queue.
if (!vis[adj[p].get(i)] &&
v[adj[p].get(i)] == 0)
{
count++;
vis[adj[p].get(i)] = true;
q.add(adj[p].get(i));
}
// When the adjacent city is not visited
// but blocked so the blocked city is
// not pushed in queue
else if (!vis[adj[p].get(i)] &&
v[adj[p].get(i)] == 1)
{
count++;
}
}
q.remove();
}
return count + 1;
}
// Utility function to perform BFS
static int bfs(int N, int v[],
Vector<Integer> adj[])
{
boolean []vis = new boolean[N + 1];
int max = 1, res;
// Marking visited array false
for(int i = 1; i <= N; i++)
vis[i] = false;
// Check for each and every city
for(int i = 1; i <= N; i++)
{
// Checks that city is not blocked
// and not visited.
if (v[i] == 0 && !vis[i])
{
res = bfsUtil(v, vis, adj, i);
if (res > max)
{
max = res;
}
}
}
return max;
}
// Driver Code
public static void main(String[] args)
{
// Denotes the number of cities
int N = 4;
@SuppressWarnings("unchecked")
Vector<Integer> []adj = new Vector[N + 1];
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
int []v = new int[N + 1];
// Adjacency list denoting road
// between city u and v
adj[1].add(2);
adj[2].add(1);
adj[2].add(3);
adj[3].add(2);
adj[3].add(4);
adj[4].add(3);
// Array for storing whether ith
// city is blocked or not
v[1] = 0;
v[2] = 1;
v[3] = 1;
v[4] = 0;
System.out.print(bfs(N, v, adj));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to solve water # supply problem using BFS # Function to perform BFS def bfsUtil(v, vis, adj, src): # Mark current source visited vis[src] = True # Queue for BFS q = [] # Push src to queue q.append(src) count = 0 while (len(q) != 0): p = q[0] for i in range(len(adj[p])): # When the adjacent city not visited and # not blocked, push city in the queue. if (vis[adj[p][i]] == False and v[adj[p][i]] == 0): count += 1 vis[adj[p][i]] = True q.push(adj[p][i]) # when the adjacent city is not visited # but blocked so the blocked city is # not pushed in queue elif(vis[adj[p][i]] == False and v[adj[p][i]] == 1): count += 1 q.remove(q[0]) return count + 1 # Utility function to perform BFS def bfs(N, v, adj): vis = [ 0 for i in range(N + 1)] mx = 1 # marking visited array false for i in range(1, N + 1, 1): vis[i] = False # Check for each and every city for i in range(1, N + 1, 1): # Checks that city is not blocked # and not visited. if (v[i] == 0 and vis[i] == False): res = bfsUtil(v, vis, adj, i) if (res > mx): mx = res return mx # Driver Code if __name__ == '__main__': N = 4 # Denotes the number of cities adj = [[] for i in range(N + 1)] v = [0 for i in range(N + 1)] # Adjacency list denoting road # between city u and v adj[1].append(2) adj[2].append(1) adj[2].append(3) adj[3].append(2) adj[3].append(4) adj[4].append(3) # array for storing whether ith # city is blocked or not v[1] = 0 v[2] = 1 v[3] = 1 v[4] = 0 print(bfs(N, v, adj)) # This code is contributed by Bhupendra_Singh
C#
// C# program to solve water
// supply problem using BFS
using System;
using System.Collections.Generic;
class GFG{
// Function to perform BFS
static int bfsUtil(int []v, bool []vis,
List<int> []adj,
int src)
{
// Mark current source visited
vis[src] = true;
// Queue for BFS
Queue<int> q = new Queue<int>();
// Push src to queue
q.Enqueue(src);
int count = 0;
while (q.Count != 0)
{
int p = q.Peek();
for(int i = 0; i < adj[p].Count; i++)
{
// When the adjacent city not
// visited and not blocked, push
// city in the queue.
if (!vis[adj[p][i]] &&
v[adj[p][i]] == 0)
{
count++;
vis[adj[p][i]] = true;
q.Enqueue(adj[p][i]);
}
// When the adjacent city is not visited
// but blocked so the blocked city is
// not pushed in queue
else if (!vis[adj[p][i]] &&
v[adj[p][i]] == 1)
{
count++;
}
}
q.Dequeue();
}
return count + 1;
}
// Utility function to perform BFS
static int bfs(int N, int []v,
List<int> []adj)
{
bool []vis = new bool[N + 1];
int max = 1, res;
// Marking visited array false
for(int i = 1; i <= N; i++)
vis[i] = false;
// Check for each and every city
for(int i = 1; i <= N; i++)
{
// Checks that city is not blocked
// and not visited.
if (v[i] == 0 && !vis[i])
{
res = bfsUtil(v, vis, adj, i);
if (res > max)
{
max = res;
}
}
}
return max;
}
// Driver Code
public static void Main(String[] args)
{
// Denotes the number of cities
int N = 4;
List<int> []adj = new List<int>[N + 1];
for (int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
int []v = new int[N + 1];
// Adjacency list denoting road
// between city u and v
adj[1].Add(2);
adj[2].Add(1);
adj[2].Add(3);
adj[3].Add(2);
adj[3].Add(4);
adj[4].Add(3);
// Array for storing whether ith
// city is blocked or not
v[1] = 0;
v[2] = 1;
v[3] = 1;
v[4] = 0;
Console.Write(bfs(N, v, adj));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to solve water
// supply problem using BFS
// Function to perform BFS
function bfsUtil(v, vis, adj, src)
{
// Mark current source visited
vis[src] = true;
// Queue for BFS
let q = [];
// Push src to queue
q.push(src);
let count = 0;
while (q.length > 0)
{
let p = q[0];
for(let i = 0; i < adj[p].length; i++)
{
// When the adjacent city not
// visited and not blocked, push
// city in the queue.
if (!vis[adj[p][i]] &&
v[adj[p][i]] == 0)
{
count++;
vis[adj[p][i]] = true;
q.add(adj[p][i]);
}
// When the adjacent city is not visited
// but blocked so the blocked city is
// not pushed in queue
else if (!vis[adj[p][i]] &&
v[adj[p][i]] == 1)
{
count++;
}
}
q.shift();
}
return count + 1;
}
// Utility function to perform BFS
function bfs(N, v, adj)
{
let vis = new Array(N + 1);
let max = 1, res;
// Marking visited array false
for(let i = 1; i <= N; i++)
vis[i] = false;
// Check for each and every city
for(let i = 1; i <= N; i++)
{
// Checks that city is not blocked
// and not visited.
if (v[i] == 0 && !vis[i])
{
res = bfsUtil(v, vis, adj, i);
if (res > max)
{
max = res;
}
}
}
return max;
}
// Denotes the number of cities
let N = 4;
let adj = new Array(N + 1);
for (let i = 0; i < adj.length; i++)
adj[i] = [];
let v = new Array(N + 1);
// Adjacency list denoting road
// between city u and v
adj[1].push(2);
adj[2].push(1);
adj[2].push(3);
adj[3].push(2);
adj[3].push(4);
adj[4].push(3);
// Array for storing whether ith
// city is blocked or not
v[1] = 0;
v[2] = 1;
v[3] = 1;
v[4] = 0;
document.write(bfs(N, v, adj));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por _shreya_garg_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA