Dado un gráfico dirigido representado como una array de adyacencia y un número entero ‘k’, la tarea es encontrar todos los pares de vértices que están conectados exactamente con aristas ‘k’.
Además, encuentre el número de formas en que los dos vértices se pueden unir en exactamente k aristas.
Ejemplos:
Input : k = 3 and graph : 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 Output : 1 -> 4 in 1 way(s) 1 -> 5 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 3 -> 2 in 1 way(s) 3 -> 4 in 1 way(s) 3 -> 5 in 1 way(s) 4 -> 3 in 1 way(s) 5 -> 1 in 1 way(s) 5 -> 3 in 1 way(s) Input : k = 2 and graph : 0 0 0 1 0 1 0 1 0 Output : 2 -> 2 in 1 way(s) 3 -> 1 in 1 way(s) 3 -> 3 in 1 way(s)
Acercarse :
- Multiplicaremos la array de adyacencia consigo misma ‘k’ número de veces.
- En la array resultante, res[i][j] será el número de formas en que se puede alcanzar el vértice ‘j’ desde el vértice ‘i’ cubriendo exactamente las aristas ‘k’.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to multiply two square matrices
vector<vector<int>> multiplyMatrices(
vector<vector<int>> arr1,
vector<vector<int>> arr2)
{
int order = arr1.size();
vector<vector<int>> ans(order, vector<int>(order));
for(int i = 0; i < order; i++)
{
for(int j = 0; j < order; j++)
{
for(int k = 0; k < order; k++)
{
ans[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
void solve(vector<vector<int>> arr, int k)
{
vector<vector<int>> res(
arr.size(), vector<int>(arr[0].size()));
// Copying arr to res,
// which is the result for k=1
for(int i = 0; i < res.size(); i++)
for(int j = 0; j < res.size(); j++)
res[i][j] = arr[i][j];
// Multiplying arr with itself
// the required number of times
for(int i = 2; i <= k; i++)
res = multiplyMatrices(res, arr);
for(int i = 0; i < res.size(); i++)
for(int j = 0; j < res.size(); j++)
// If there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i][j] > 0)
{
cout << i << " -> " << j
<< " in " << res[i][j]
<< " way(s)" << endl;
}
}
// Driver code
int main(int argc, char const *argv[])
{
vector<vector<int>> arr(5, vector<int>(5));
arr[0][1] = 1;
arr[1][2] = 1;
arr[2][3] = 1;
arr[2][4] = 1;
arr[3][0] = 1;
arr[4][2] = 1;
int k = 3;
solve(arr, k);
}
// This code is contributed by sanjeev2552
Java
// Java implementation of the approach
public class KPaths {
// Function to multiply two square matrices
static int[][] multiplyMatrices(int[][] arr1, int[][] arr2)
{
int order = arr1.length;
int[][] ans = new int[order][order];
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
for (int k = 0; k < order; k++) {
ans[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
static void solve(int[][] arr, int k)
{
int[][] res = new int[arr.length][arr[0].length];
// copying arr to res,
// which is the result for k=1
for (int i = 0; i < res.length; i++)
for (int j = 0; j < res.length; j++)
res[i][j] = arr[i][j];
// multiplying arr with itself
// the required number of times
for (int i = 2; i <= k; i++)
res = multiplyMatrices(res, arr);
for (int i = 0; i < res.length; i++)
for (int j = 0; j < res.length; j++)
// if there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i][j] > 0)
System.out.println(i + " -> " + j + " in " + res[i][j] + " way(s)");
}
// Driver code
public static void main(String[] args)
{
int[][] arr = new int[5][5];
arr[0][1] = 1;
arr[1][2] = 1;
arr[2][3] = 1;
arr[2][4] = 1;
arr[3][0] = 1;
arr[4][2] = 1;
int k = 3;
solve(arr, k);
}
}
Python3
# Python3 implementation of the approach # Function to multiply two square matrices def multiplyMatrices(arr1, arr2): order = len(arr1) ans = [[0 for i in range(order)] for j in range(order)] for i in range(order): for j in range(order): for k in range(order): ans[i][j] += arr1[i][k] * arr2[k][j] return ans # Function to find all the pairs that # can be connected with exactly 'k' edges def solve(arr, k): res = [[0 for i in range(len(arr))] for j in range(len(arr))] # Copying arr to res, # which is the result for k=1 for i in range(len(arr)): for j in range(len(arr)): res[i][j] = arr[i][j] # Multiplying arr with itself # the required number of times for i in range(2, k+1): res = multiplyMatrices(res, arr) for i in range(len(arr)): for j in range(len(arr)): # If there is a path between 'i' # and 'j' in exactly 'k' edges if (res[i][j] > 0): print(i, "->", j, "in", res[i][j], "way(s)") # Driver Code if __name__ == "__main__": arr = [1, 2, 3, 4] arr = [[0 for i in range(5)] for j in range(5)] arr[0][1] = 1 arr[1][2] = 1 arr[2][3] = 1 arr[2][4] = 1 arr[3][0] = 1 arr[4][2] = 1 k = 3 solve(arr, k) # This code is contributed by kirtishsurangalikar
C#
// C# implementation of the approach
using System;
class KPaths
{
// Function to multiply two square matrices
static int[,] multiplyMatrices(int[,] arr1,
int[,] arr2)
{
int order = arr1.GetLength(0);
int[,] ans = new int[order, order];
for (int i = 0; i < order; i++)
{
for (int j = 0; j < order; j++)
{
for (int k = 0; k < order; k++)
{
ans[i, j] += arr1[i, k] *
arr2[k, j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
static void solve(int[,] arr, int k)
{
int[,] res = new int[arr.GetLength(0),
arr.GetLength(1)];
// copying arr to res,
// which is the result for k = 1
for (int i = 0; i < res.GetLength(0); i++)
for (int j = 0; j < res.GetLength(1); j++)
res[i, j] = arr[i, j];
// multiplying arr with itself
// the required number of times
for (int i = 2; i <= k; i++)
res = multiplyMatrices(res, arr);
for (int i = 0; i < res.GetLength(0); i++)
for (int j = 0; j < res.GetLength(1); j++)
// if there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i,j] > 0)
Console.WriteLine(i + " -> " + j + " in " +
res[i, j] + " way(s)");
}
// Driver code
public static void Main(String[] args)
{
int[,] arr = new int[5, 5];
arr[0, 1] = 1;
arr[1, 2] = 1;
arr[2, 3] = 1;
arr[2, 4] = 1;
arr[3, 0] = 1;
arr[4, 2] = 1;
int k = 3;
solve(arr, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the approach
// Function to multiply two square matrices
function multiplyMatrices(arr1, arr2)
{
var order = arr1.length;
var ans = Array(order).fill(0).map(x => Array(order).fill(0));
for (var i = 0; i < order; i++) {
for (var j = 0; j < order; j++) {
for (var k = 0; k < order; k++) {
ans[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
function solve(arr , k)
{
var res = Array(arr.length).fill(0).map(x => Array(arr[0].length).fill(0));
// copying arr to res,
// which is the result for k=1
for (var i = 0; i < res.length; i++)
for (var j = 0; j < res.length; j++)
res[i][j] = arr[i][j];
// multiplying arr with itself
// the required number of times
for (var i = 2; i <= k; i++)
res = multiplyMatrices(res, arr);
for (var i = 0; i < res.length; i++)
for (var j = 0; j < res.length; j++)
// if there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i][j] > 0)
document.write(i + " -> " + j + " in " + res[i][j] + " way(s)<br>");
}
// Driver code
var arr = Array(5).fill(0).map(x => Array(5).fill(0));
arr[0][1] = 1;
arr[1][2] = 1;
arr[2][3] = 1;
arr[2][4] = 1;
arr[3][0] = 1;
arr[4][2] = 1;
var k = 3;
solve(arr, k);
// This code is contributed by shikhasingrajput
</script>
Producción
0 -> 3 in 1 way(s) 0 -> 4 in 1 way(s) 1 -> 0 in 1 way(s) 1 -> 2 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 2 -> 4 in 1 way(s) 3 -> 2 in 1 way(s) 4 -> 0 in 1 way(s) 4 -> 2 in 1 way(s)
La complejidad temporal del código anterior se puede reducir para valores grandes de k mediante el uso de exponenciación matricial . La complejidad se puede cambiar de O(n^3 * k) a O(n^3 * log k)
C++
#include <iostream>
#include <vector>
using namespace std;
// Function to multiply two square matrices
static vector<vector<int> >
multiplyMatrices(vector<vector<int> > &arr1,
vector<vector<int> > &arr2)
{
int order = arr1.size();
vector<vector<int> > ans(order, vector<int>(order));
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
for (int k = 0; k < order; k++) {
ans[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return ans;
}
vector<vector<int> > identity(int n)
{
vector<vector<int> > r(n, vector<int>(n));
for (int i = 0; i < n; i++)
r[i][i] = 1;
return r;
}
vector<vector<int> > power(vector<vector<int> >& x, int y,
int n)
{
vector<vector<int> > res = identity(n);
while (y > 0) {
if ((y & 1) == 1)
res = multiplyMatrices(res, x);
// y must be even now
// y = y / 2
y = y >> 1;
x = multiplyMatrices(x, x);
}
return res;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
void solve(vector<vector<int> > &arr, int k)
{
vector<vector<int> > res(arr.size(),
vector<int>(arr[0].size()));
res = power(arr, k, arr[0].size());
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res.size(); j++) {
// if there is a path between 'i' and 'j' in
// exactly 'k' edges
if (res[i][j] > 0) {
cout << i << " -> " << j << " in "
<< res[i][j] << " way(s)" << endl;
}
}
}
}
int main()
{
vector<vector<int> > arr(5, vector<int>(5));
arr[0][1] = 1;
arr[1][2] = 1;
arr[2][3] = 1;
arr[2][4] = 1;
arr[3][0] = 1;
arr[4][2] = 1;
int k = 3;
solve(arr, k);
return 0;
}
// This code is contributed by Tapesh (tapeshdua420)
Java
class KPaths {
// Function to multiply two square matrices
static int[][] multiplyMatrices(int[][] arr1, int[][] arr2)
{
int order = arr1.length;
int[][] ans = new int[order][order];
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
for (int k = 0; k < order; k++) {
ans[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
static void solve(int[][] arr, int k)
{
int[][] res = new int[arr.length][arr[0].length];
res = power(arr, k, arr[0].length);
for (int i = 0; i < res.length; i++)
for (int j = 0; j < res.length; j++)
// if there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i][j] > 0)
System.out.println(i + " -> " + j + " in " + res[i][j] + " way(s)");
}
static int[][] power(int x[][], int y, int n)
{
// MATRIX EXPONENTIATION
// Initialize result
int res[][] = identity(n);
while (y > 0) {
if ((y & 1) == 1)
res = multiplyMatrices(res, x);
// y must be even now
// y = y / 2
y = y >> 1;
x = multiplyMatrices(x, x);
}
return res;
}
static int[][] identity(int n)
{
// returns identity matrix of order n
int r[][] = new int[n][n];
for (int i = 0; i < n; i++)
r[i][i] = 1;
return r;
}
// Driver code
public static void main(String[] args)
{
int[][] arr = new int[5][5];
arr[0][1] = 1;
arr[1][2] = 1;
arr[2][3] = 1;
arr[2][4] = 1;
arr[3][0] = 1;
arr[4][2] = 1;
int k = 3;
solve(arr, k);
}
}
Python3
# Function to multiply two square matrices
def multiplyMatrices(arr1, arr2):
order = len(arr1)
ans = [[0 for i in range(order)] for j in range(order)]
for i in range(order):
for j in range(order):
for k in range(order):
ans[i][j] += arr1[i][k] * arr2[k][j]
return ans
def identity(n):
r = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
r[i][i] = 1
return r
def power(x, y, n):
res = identity(n)
while y > 0:
if ((y & 1) == 1):
res = multiplyMatrices(res, x)
# y must be even now
y = y >> 1
x = multiplyMatrices(x, x)
return res
# Function to find all the pairs that
# can be connected with exactly 'k' edges
def solve(arr, k):
res = [[0 for i in range(len(arr))] for j in range(len(arr))]
res = power(arr, k, len(arr[0]))
for i in range(len(res)):
for j in range(len(res)):
# if there is a path between 'i' and 'j' in
# exactly 'k' edges
if res[i][j] > 0:
print("{} -> {} in {} way(s)".format(i, j, res[i][j]))
if __name__ == "__main__":
arr = [[0 for i in range(5)] for j in range(5)]
arr[0][1] = 1
arr[1][2] = 1
arr[2][3] = 1
arr[2][4] = 1
arr[3][0] = 1
arr[4][2] = 1
k = 3
solve(arr, k)
# This code is contributed by Tapesh (tapeshdua420)
C#
// C# implementation of the above approach:
using System;
class KPaths
{
// Function to multiply two square matrices
static int[,] multiplyMatrices(int[,] arr1,
int[,] arr2)
{
int order = arr1.GetLength(0);
int[,] ans = new int[order,order];
for (int i = 0; i < order; i++)
{
for (int j = 0; j < order; j++)
{
for (int k = 0; k < order; k++)
{
ans[i, j] += arr1[i, k] *
arr2[k, j];
}
}
}
return ans;
}
// Function to find all the pairs that
// can be connected with exactly 'k' edges
static void solve(int[,] arr, int k)
{
int[,] res = new int[arr.GetLength(0),
arr.GetLength(1)];
res = power(arr, k, arr.GetLength(0));
for (int i = 0; i < res.GetLength(0); i++)
for (int j = 0; j < res.GetLength(1); j++)
// if there is a path between 'i'
// and 'j' in exactly 'k' edges
if (res[i, j] > 0)
Console.WriteLine(i + " -> " + j +
" in " + res[i, j] + " way(s)");
}
static int[,] power(int [,]x, int y, int n)
{
// MATRIX EXPONENTIATION
// Initialize result
int [,]res = identity(n);
while (y > 0)
{
if ((y & 1) == 1)
res = multiplyMatrices(res, x);
// y must be even now
// y = y / 2
y = y >> 1;
x = multiplyMatrices(x, x);
}
return res;
}
static int[,] identity(int n)
{
// returns identity matrix of order n
int [,]r = new int[n, n];
for (int i = 0; i < n; i++)
r[i, i] = 1;
return r;
}
// Driver code
public static void Main(String[] args)
{
int[,] arr = new int[5, 5];
arr[0, 1] = 1;
arr[1, 2] = 1;
arr[2, 3] = 1;
arr[2, 4] = 1;
arr[3, 0] = 1;
arr[4, 2] = 1;
int k = 3;
solve(arr, k);
}
}
// This code is contributed by PrinciRaj1992
Producción
0 -> 3 in 1 way(s) 0 -> 4 in 1 way(s) 1 -> 0 in 1 way(s) 1 -> 2 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 2 -> 4 in 1 way(s) 3 -> 2 in 1 way(s) 4 -> 0 in 1 way(s) 4 -> 2 in 1 way(s)
Análisis de Complejidad:
Complejidad de tiempo: O(n 3 * logk)
Complejidad espacial: O(n 2 )