Dado un gráfico con N Nodes y K aristas bidireccionales entre ellos, encuentre el número de Nodes que se pueden alcanzar desde un particular. Se dice que dos Nodes X e Y son alcanzables si podemos comenzar en X y terminar en Y usando cualquier número de aristas.
Nota: un Node es accesible a sí mismo.
Input : N = 7
1 5
\ / \
2 6 __ 7
\
3
\
4
Output :4 4 4 4 3 3 3
From node 1 ,nodes {1,2,3,4} can be visited
hence the answer is equal to 4
From node 5,nodes {5,6,7} can be visited.
hence the answer is equal to 3.
Similarly, print the count for every node.
Input : N = 8
1 7
/ \ \
2 3 8
\ / \
5 6
Output :6 6 6 6 6 6 2 2
Enfoque:
para encontrar el número de Nodes accesibles desde un Node en particular, una cosa a observar es que podemos llegar desde un Node X a un Node Y solo cuando están en el mismo componente conectado.
Dado que el gráfico es bidireccional, cualquier Node en un componente conexo a cualquier otro Node en los mismos componentes conexos. Por lo tanto, para un Node en particular, el número X de Nodes a los que se podrá acceder será el número de Nodes en ese componente en particular. Utilice la búsqueda en profundidad para encontrar la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
// Function to perform the DFS calculating the
// count of the elements in a connected component
void dfs(int curr, int& cnt, vector<int>&
visited, vector<int>& duringdfs)
{
visited[curr] = 1;
// Number of nodes in this component
++cnt;
// Stores the nodes which belong
// to current component
duringdfs.push_back(curr);
for (auto& child : graph[curr]) {
// If the child is not visited
if (visited[child] == 0) {
dfs(child, cnt, visited, duringdfs);
}
}
}
// Function to return the desired
// count for every node in the graph
void MaximumVisit(int n, int k)
{
// To keep track of nodes we visit
vector<int> visited(n+1,0);
// No of connected elements for each node
vector<int> ans(n+1);
vector<int> duringdfs;
for (int i = 1; i <= n; ++i) {
duringdfs.clear();
int cnt = 0;
// If a node is not visited, perform a DFS as
// this node belongs to a different component
// which is not yet visited
if (visited[i] == 0) {
cnt = 0;
dfs(i, cnt, visited, duringdfs);
}
// Now store the count of all the visited
// nodes for any particular component.
for (auto& x : duringdfs) {
ans[x] = cnt;
}
}
// Print the result
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
return;
}
// Function to build the graph
void MakeGraph(){
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
graph[3].push_back(4);
graph[4].push_back(3);
graph[5].push_back(6);
graph[6].push_back(5);
graph[6].push_back(7);
graph[7].push_back(6);
graph[5].push_back(7);
graph[7].push_back(5);
}
// Driver code
int main()
{
int N = 7, K = 6;
graph.resize(N+1);
// Build the graph
MakeGraph();
MaximumVisit(N, K);
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
class GFG
{
static final int maxx = 100005;
@SuppressWarnings("unchecked")
static Vector<Integer>[] graph = new Vector[maxx];
static Vector<Integer> duringdfs = new Vector<>();
static int cnt = 0;
// Function to perform the DFS calculating the
// count of the elements in a connected component
static void dfs(int curr, int[] visited)
{
visited[curr] = 1;
// Number of nodes in this component
++cnt;
// Stores the nodes which belong
// to current component
duringdfs.add(curr);
for (int child : graph[curr])
{
// If the child is not visited
if (visited[child] == 0)
dfs(child, visited);
}
}
// Function to return the desired
// count for every node in the graph
static void maximumVisit(int n, int k)
{
// To keep track of nodes we visit
int[] visited = new int[maxx];
// Mark every node unvisited
Arrays.fill(visited, 0);
int[] ans = new int[maxx];
// No of connected elements for each node
Arrays.fill(ans, 0);
for (int i = 1; i <= n; i++)
{
duringdfs.clear();
// If a node is not visited, perform a DFS as
// this node belongs to a different component
// which is not yet visited
if (visited[i] == 0)
{
cnt = 0;
dfs(i, visited);
}
// Now store the count of all the visited
// nodes for any particular component.
for (int x : duringdfs)
ans[x] = cnt;
}
// Print the result
for (int i = 1; i <= n; i++)
System.out.print(ans[i] + " ");
System.out.println();
return;
}
// Function to build the graph
static void makeGraph()
{
// Initializing graph
for (int i = 0; i < maxx; i++)
graph[i] = new Vector<>();
graph[1].add(2);
graph[2].add(1);
graph[2].add(3);
graph[3].add(2);
graph[3].add(4);
graph[4].add(3);
graph[5].add(6);
graph[6].add(5);
graph[6].add(7);
graph[7].add(6);
graph[5].add(7);
graph[7].add(5);
}
// Driver Code
public static void main(String[] args)
{
int N = 7, K = 6;
// Build the graph
makeGraph();
maximumVisit(N, K);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the above approach maxx = 100005 graph = [[] for i in range(maxx)] # Function to perform the DFS calculating the # count of the elements in a connected component def dfs(curr, cnt, visited, duringdfs): visited[curr] = 1 # Number of nodes in this component cnt += 1 # Stores the nodes which belong # to current component duringdfs.append(curr) for child in graph[curr]: # If the child is not visited if (visited[child] == 0): cnt, duringdfs = dfs(child, cnt, visited, duringdfs) return cnt, duringdfs # Function to return the desired # count for every node in the graph def MaximumVisit(n, k): # To keep track of nodes we visit visited = [0 for i in range(maxx)] ans = [0 for i in range(maxx)] duringdfs = [] for i in range(1, n + 1): duringdfs.clear() cnt = 0 # If a node is not visited, perform a DFS as # this node belongs to a different component # which is not yet visited if (visited[i] == 0): cnt = 0 cnt, duringdfs = dfs(i, cnt, visited, duringdfs) # Now store the count of all the visited # nodes for any particular component. for x in duringdfs: ans[x] = cnt # Print the result for i in range(1, n + 1): print(ans[i], end = ' ') print() return # Function to build the graph def MakeGraph(): graph[1].append(2) graph[2].append(1) graph[2].append(3) graph[3].append(2) graph[3].append(4) graph[4].append(3) graph[5].append(6) graph[6].append(5) graph[6].append(7) graph[7].append(6) graph[5].append(7) graph[7].append(5) # Driver code if __name__=='__main__': N = 7 K = 6 # Build the graph MakeGraph() MaximumVisit(N, K) # This code is contributed by rutvik_56
C#
// C# implementation of the above approach
using System;
using System.Collections;
class GFG{
static int maxx = 100005;
static ArrayList[] graph = new ArrayList[maxx];
static ArrayList duringdfs = new ArrayList();
static int cnt = 0;
// Function to perform the DFS calculating the
// count of the elements in a connected component
static void dfs(int curr, int[] visited)
{
visited[curr] = 1;
// Number of nodes in this component
++cnt;
// Stores the nodes which belong
// to current component
duringdfs.Add(curr);
foreach(int child in graph[curr])
{
// If the child is not visited
if (visited[child] == 0)
dfs(child, visited);
}
}
// Function to return the desired
// count for every node in the graph
static void maximumVisit(int n, int k)
{
// To keep track of nodes we visit
int[] visited = new int[maxx];
// Mark every node unvisited
Array.Fill(visited, 0);
int[] ans = new int[maxx];
// No of connected elements for each node
Array.Fill(ans, 0);
for(int i = 1; i <= n; i++)
{
duringdfs.Clear();
// If a node is not visited, perform
// a DFS as this node belongs to a
// different component which is not
// yet visited
if (visited[i] == 0)
{
cnt = 0;
dfs(i, visited);
}
// Now store the count of all the visited
// nodes for any particular component.
foreach(int x in duringdfs)
ans[x] = cnt;
}
// Print the result
for(int i = 1; i <= n; i++)
Console.Write(ans[i] + " ");
Console.WriteLine();
return;
}
// Function to build the graph
static void makeGraph()
{
// Initializing graph
for(int i = 0; i < maxx; i++)
graph[i] = new ArrayList();
graph[1].Add(2);
graph[2].Add(1);
graph[2].Add(3);
graph[3].Add(2);
graph[3].Add(4);
graph[4].Add(3);
graph[5].Add(6);
graph[6].Add(5);
graph[6].Add(7);
graph[7].Add(6);
graph[5].Add(7);
graph[7].Add(5);
}
// Driver Code
public static void Main(string[] args)
{
int N = 7, K = 6;
// Build the graph
makeGraph();
maximumVisit(N, K);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript implementation of the above approach
let maxx = 100005;
let graph = new Array(maxx);
for(let i = 0; i < maxx; i++)
{
graph[i] = [];
}
let duringdfs = [];
let cnt = 0;
// Function to perform the DFS calculating the
// count of the elements in a connected component
function dfs(curr, visited)
{
visited[curr] = 1;
// Number of nodes in this component
++cnt;
// Stores the nodes which belong
// to current component
duringdfs.push(curr);
for(let child = 0; child < graph[curr].length; child++)
{
// If the child is not visited
if (visited[graph[curr][child]] == 0)
dfs(graph[curr][child], visited);
}
}
// Function to return the desired
// count for every node in the graph
function maximumVisit(n, k)
{
// To keep track of nodes we visit
let visited = new Array(maxx);
// Mark every node unvisited
visited.fill(0);
let ans = new Array(maxx);
// No of connected elements for each node
ans.fill(0);
for(let i = 1; i <= n; i++)
{
duringdfs = [];
// If a node is not visited, perform
// a DFS as this node belongs to a
// different component which is not
// yet visited
if (visited[i] == 0)
{
cnt = 0;
dfs(i, visited);
}
// Now store the count of all the visited
// nodes for any particular component.
for(let x = 0; x < duringdfs.length; x++)
ans[duringdfs[x]] = cnt;
}
// Print the result
for(let i = 1; i <= n; i++)
document.write(ans[i] + " ");
document.write("</br>");
return;
}
// Function to build the graph
function makeGraph()
{
// Initializing graph
for(let i = 0; i < maxx; i++)
graph[i] = [];
graph[1].push(2);
graph[2].push(1);
graph[2].push(3);
graph[3].push(2);
graph[3].push(4);
graph[4].push(3);
graph[5].push(6);
graph[6].push(5);
graph[6].push(7);
graph[7].push(6);
graph[5].push(7);
graph[7].push(5);
}
let N = 7, K = 6;
// Build the graph
makeGraph();
maximumVisit(N, K);
// This code is contributed by divyesh072019.
</script>
Producción:
4 4 4 4 3 3 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)