Dado un gráfico no dirigido de N vértices y M aristas, la tarea es asignar direcciones a las M aristas dadas de modo que el gráfico se convierta en Componentes fuertemente conectados . Si un gráfico no se puede convertir en componentes fuertemente conectados, imprima «-1» .
Ejemplos:
Entrada: N = 5, Edges[][] = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } }
Salida :
0->1
2->0
4->1
3->4
2->3
1->2
Explicación:
A continuación se muestran los bordes asignados al gráfico no dirigido anterior:
Entrada: N = 5, Edges[][] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, { 3, 4 } }
Salida: -1
Explicación:
A continuación es el gráfico de la información anterior:
Dado que hay un puente presente en el gráfico anterior no dirigido. Por lo tanto, este gráfico no se puede convertir en SCC.
Enfoque: sabemos que en cualquier gráfico dirigido se dice que está en componentes fuertemente conectados (SCC) si y solo si todos los vértices del gráfico son parte de algún ciclo. El gráfico no dirigido dado no forma SCC si y solo si el gráfico contiene algún puente . A continuación se muestran los pasos:
- Usaremos una array mark[] para almacenar el Node visitado durante DFS Traversal, order[] para almacenar el número de índice del Node visitado y bridge_detect[] para almacenar cualquier puente presente en el gráfico dado.
- Inicie el DFS Traversal desde el vértice 1 .
- Recorra la lista de Adyacencia del Node actual y haga lo siguiente:
- Si algún borde se atraviesa de nuevo durante cualquier llamada DFS, entonces ignore ese borde.
- Si el orden del Node secundario ( Node u ) es mayor que el orden del Node principal ( Node v ), ignore estos bordes actuales, ya que los bordes (v, u) ya están procesados.
- Si se encuentra algún borde posterior, actualice los bordes del puente del Node principal actual ( Node v ) como:
bridge_detect[v] = min(order[u], bridge_detect[v]);
- De lo contrario, realice el DFS Traversal para el Node secundario actual y repita el paso 3 para el Node actual.
- Actualice la detección de puentes después de la llamada DFS para el Node actual como:
bridge_detect[v] = min(bridge_detect[u], bridge_detect[v])
- Almacene el par actual de bordes (v, u) como bordes dirigidos desde el Node v al Node u en una array de pares (por ejemplo , arr[][] ).
- Si hay algún puente presente en el gráfico dado, imprima «-1» .
- De lo contrario, imprima los bordes dirigidos almacenados en arr[][] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// To store the assigned Edges
vector<pair<int, int> > ans;
// Flag variable to check Bridges
int flag = 1;
// Function to implement DFS Traversal
int dfs(vector<int> adj[],
int* order, int* bridge_detect,
bool* mark, int v, int l)
{
// Mark the current node as visited
mark[v] = 1;
// Update the order of node v
order[v] = order[l] + 1;
// Update the bridge_detect for node v
bridge_detect[v] = order[v];
// Traverse the adjacency list of
// Node v
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
// Ignores if same edge is traversed
if (u == l) {
continue;
}
// Ignores the edge u --> v as
// v --> u is already processed
if (order[v] < order[u]) {
continue;
}
// Finds a back Edges, cycle present
if (mark[u]) {
// Update the bridge_detect[v]
bridge_detect[v]
= min(order[u],
bridge_detect[v]);
}
// Else DFS traversal for current
// node in the adjacency list
else {
dfs(adj, order, bridge_detect,
mark, u, v);
}
// Update the bridge_detect[v]
bridge_detect[v]
= min(bridge_detect[u],
bridge_detect[v]);
// Store the current directed Edge
ans.push_back(make_pair(v, u));
}
// Condition for Bridges
if (bridge_detect[v] == order[v]
&& l != 0) {
flag = 0;
}
// Return flag
return flag;
}
// Function to print the direction
// of edges to make graph SCCs
void convert(vector<int> adj[], int n)
{
// Arrays to store the visited,
// bridge_detect and order of
// Nodes
int order[n] = { 0 };
int bridge_detect[n] = { 0 };
bool mark[n];
// Initialise marks[] as false
memset(mark, false, sizeof(mark));
// DFS Traversal from vertex 1
int flag = dfs(adj, order,
bridge_detect,
mark, 1, 0);
// If flag is zero, then Bridge
// is present in the graph
if (flag == 0) {
cout << "-1";
}
// Else print the direction of
// Edges assigned
else {
for (auto& it : ans) {
cout << it.first << "->"
<< it.second << '\n';
}
}
}
// Function to create graph
void createGraph(int Edges[][2],
vector<int> adj[],
int M)
{
// Traverse the Edges
for (int i = 0; i < M; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
// Push the edges in an
// adjacency list
adj[u].push_back(v);
adj[v].push_back(u);
}
}
// Driver Code
int main()
{
// N vertices and M Edges
int N = 5, M = 6;
int Edges[M][2]
= { { 0, 1 }, { 0, 2 },
{ 1, 2 }, { 1, 4 },
{ 2, 3 }, { 3, 4 } };
// To create Adjacency List
vector<int> adj[N];
// Create an undirected graph
createGraph(Edges, adj, M);
// Function Call
convert(adj, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// To store the assigned Edges
static ArrayList<int[]> ans;
// Flag variable to check Bridges
static int flag = 1;
// Function to implement DFS Traversal
static int dfs(ArrayList<ArrayList<Integer>> adj,
int[] order, int[] bridge_detect,
boolean[] mark, int v, int l)
{
// Mark the current node as visited
mark[v] = true;
// Update the order of node v
order[v] = order[l] + 1;
// Update the bridge_detect for node v
bridge_detect[v] = order[v];
// Traverse the adjacency list of
// Node v
for(int i = 0; i < adj.get(v).size(); i++)
{
int u = adj.get(v).get(i);
// Ignores if same edge is traversed
if (u == l)
{
continue;
}
// Ignores the edge u --> v as
// v --> u is already processed
if (order[v] < order[u])
{
continue;
}
// Finds a back Edges, cycle present
if (mark[u])
{
// Update the bridge_detect[v]
bridge_detect[v] = Math.min(order[u],
bridge_detect[v]);
}
// Else DFS traversal for current
// node in the adjacency list
else
{
dfs(adj, order, bridge_detect,
mark, u, v);
}
// Update the bridge_detect[v]
bridge_detect[v] = Math.min(bridge_detect[u],
bridge_detect[v]);
// Store the current directed Edge
ans.add(new int[]{v, u});
}
// Condition for Bridges
if (bridge_detect[v] == order[v] && l != 0)
{
flag = 0;
}
// Return flag
return flag;
}
// Function to print the direction
// of edges to make graph SCCs
static void convert(ArrayList<ArrayList<Integer>> adj,
int n)
{
// Arrays to store the visited,
// bridge_detect and order of
// Nodes
int[] order = new int[n];
int[] bridge_detect = new int[n];
boolean mark[] = new boolean[n];
// DFS Traversal from vertex 1
int flag = dfs(adj, order,
bridge_detect,
mark, 1, 0);
// If flag is zero, then Bridge
// is present in the graph
if (flag == 0)
{
System.out.print("-1");
}
// Else print the direction of
// Edges assigned
else
{
for(int[] it : ans)
{
System.out.println(it[0] + "->" +
it[1]);
}
}
}
// Function to create graph
static void createGraph(int Edges[][],
ArrayList<ArrayList<Integer>> adj,
int M)
{
// Traverse the Edges
for(int i = 0; i < M; i++)
{
int u = Edges[i][0];
int v = Edges[i][1];
// Push the edges in an
// adjacency list
adj.get(u).add(v);
adj.get(v).add(u);
}
}
// Driver code
public static void main(String[] args)
{
// N vertices and M Edges
int N = 5, M = 6;
int Edges[][] = { { 0, 1 }, { 0, 2 },
{ 1, 2 }, { 1, 4 },
{ 2, 3 }, { 3, 4 } };
// To create Adjacency List
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
ans = new ArrayList<>();
for(int i = 0; i < N; i++)
adj.add(new ArrayList<>());
// Create an undirected graph
createGraph(Edges, adj, M);
// Function Call
convert(adj, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for
# the above approach
# To store the assigned
# Edges
ans = []
# Flag variable to
# check Bridges
flag = 1;
# Function to implement
# DFS Traversal
def dfs(adj, order,
bridge_detect,
mark, v, l):
global flag
# Mark the current
# node as visited
mark[v] = 1;
# Update the order of
# node v
order[v] = order[l] + 1;
# Update the bridge_detect
# for node v
bridge_detect[v] = order[v];
# Traverse the adjacency list of
# Node v
for i in range(len(adj[v])):
u = adj[v][i];
# Ignores if same edge
# is traversed
if (u == l):
continue;
# Ignores the edge u --> v as
# v --> u is already processed
if (order[v] < order[u]):
continue;
# Finds a back Edges,
# cycle present
if (mark[u]):
# Update the bridge_detect[v]
bridge_detect[v] = min(order[u],
bridge_detect[v]);
# Else DFS traversal for current
# node in the adjacency list
else:
dfs(adj, order,
bridge_detect,
mark, u, v);
# Update the bridge_detect[v]
bridge_detect[v] = min(bridge_detect[u],
bridge_detect[v]);
# Store the current
# directed Edge
ans.append([v, u]);
# Condition for Bridges
if (bridge_detect[v] ==
order[v] and l != 0):
flag = 0;
# Return flag
return flag;
# Function to print the
# direction of edges to
# make graph SCCs
def convert(adj, n):
# Arrays to store the visited,
# bridge_detect and order of
# Nodes
order = [0 for i in range(n)]
bridge_detect = [0 for i in range(n)]
mark = [False for i in range(n)]
# DFS Traversal from
# vertex 1
flag = dfs(adj, order,
bridge_detect,
mark, 1, 0);
# If flag is zero, then Bridge
# is present in the graph
if (flag == 0):
print(-1)
# Else print the direction
# of Edges assigned
else:
for it in ans:
print("{} -> {}".format(it[0],
it[1]))
# Function to create graph
def createGraph(Edges,adj, M):
# Traverse the Edges
for i in range(M):
u = Edges[i][0];
v = Edges[i][1];
# Push the edges in an
# adjacency list
adj[u].append(v);
adj[v].append(u);
# Driver code
if __name__ == "__main__":
# N vertices and M Edges
N = 5
M = 6;
Edges = [[0, 1], [0, 2],
[1, 2], [1, 4],
[2, 3], [3, 4]];
# To create Adjacency List
adj = [[] for i in range(N)]
# Create an undirected graph
createGraph(Edges, adj, M);
# Function Call
convert(adj, N);
# This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// To store the assigned Edges
static ArrayList ans;
// Flag variable to check Bridges
static int flag = 1;
// Function to implement DFS Traversal
static int dfs(ArrayList adj,
int[] order, int[] bridge_detect,
bool[] mark, int v, int l)
{
// Mark the current node as visited
mark[v] = true;
// Update the order of node v
order[v] = order[l] + 1;
// Update the bridge_detect for node v
bridge_detect[v] = order[v];
// Traverse the adjacency list of
// Node v
for(int i = 0;
i < ((ArrayList)adj[v]).Count;
i++)
{
int u = (int)((ArrayList)adj[v])[i];
// Ignores if same edge is traversed
if (u == l)
{
continue;
}
// Ignores the edge u --> v as
// v --> u is already processed
if (order[v] < order[u])
{
continue;
}
// Finds a back Edges, cycle present
if (mark[u])
{
// Update the bridge_detect[v]
bridge_detect[v] = Math.Min(order[u],
bridge_detect[v]);
}
// Else DFS traversal for current
// node in the adjacency list
else
{
dfs(adj, order, bridge_detect,
mark, u, v);
}
// Update the bridge_detect[v]
bridge_detect[v] = Math.Min(bridge_detect[u],
bridge_detect[v]);
// Store the current directed Edge
ans.Add(new int[]{v, u});
}
// Condition for Bridges
if (bridge_detect[v] == order[v] && l != 0)
{
flag = 0;
}
// Return flag
return flag;
}
// Function to print the direction
// of edges to make graph SCCs
static void convert(ArrayList adj,
int n)
{
// Arrays to store the visited,
// bridge_detect and order of
// Nodes
int[] order = new int[n];
int[] bridge_detect = new int[n];
bool []mark = new bool[n];
// DFS Traversal from vertex 1
int flag = dfs(adj, order,
bridge_detect,
mark, 1, 0);
// If flag is zero, then Bridge
// is present in the graph
if (flag == 0)
{
Console.Write("-1");
}
// Else print the direction of
// Edges assigned
else
{
foreach(int[] it in ans)
{
Console.WriteLine(it[0] + "->" +
it[1]);
}
}
}
// Function to create graph
static void createGraph(int [,]Edges,
ArrayList adj,
int M)
{
// Traverse the Edges
for(int i = 0; i < M; i++)
{
int u = Edges[i, 0];
int v = Edges[i, 1];
// Push the edges in an
// adjacency list
((ArrayList)adj[u]).Add(v);
((ArrayList)adj[v]).Add(u);
}
}
// Driver code
public static void Main(string[] args)
{
// N vertices and M Edges
int N = 5, M = 6;
int [,]Edges = { { 0, 1 }, { 0, 2 },
{ 1, 2 }, { 1, 4 },
{ 2, 3 }, { 3, 4 } };
// To create Adjacency List
ArrayList adj = new ArrayList();
ans = new ArrayList();
for(int i = 0; i < N; i++)
adj.Add(new ArrayList());
// Create an undirected graph
createGraph(Edges, adj, M);
// Function Call
convert(adj, N);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript program for the above approach
// To store the assigned Edges
let ans;
// Flag variable to check Bridges
let flag = 1;
// Function to implement DFS Traversal
function dfs(adj, order, bridge_detect, mark, v, l)
{
// Mark the current node as visited
mark[v] = true;
// Update the order of node v
order[v] = order[l] + 1;
// Update the bridge_detect for node v
bridge_detect[v] = order[v];
// Traverse the adjacency list of
// Node v
for(let i = 0; i < adj[v].length; i++)
{
let u = adj[v][i];
// Ignores if same edge is traversed
if (u == l)
{
continue;
}
// Ignores the edge u --> v as
// v --> u is already processed
if (order[v] < order[u])
{
continue;
}
// Finds a back Edges, cycle present
if (mark[u])
{
// Update the bridge_detect[v]
bridge_detect[v] = Math.min(order[u],
bridge_detect[v]);
}
// Else DFS traversal for current
// node in the adjacency list
else
{
dfs(adj, order, bridge_detect, mark, u, v);
}
// Update the bridge_detect[v]
bridge_detect[v] = Math.min(bridge_detect[u], bridge_detect[v]);
// Store the current directed Edge
ans.push([v, u]);
}
// Condition for Bridges
if (bridge_detect[v] == order[v] && l != 0)
{
flag = 0;
}
// Return flag
return flag;
}
// Function to print the direction
// of edges to make graph SCCs
function convert(adj, n)
{
// Arrays to store the visited,
// bridge_detect and order of
// Nodes
let order = new Array(n);
let bridge_detect = new Array(n);
let mark = new Array(n);
// DFS Traversal from vertex 1
let flag = dfs(adj, order, bridge_detect, mark, 1, 0);
// If flag is zero, then Bridge
// is present in the graph
if (flag == 0)
{
document.write("-1");
}
// Else print the direction of
// Edges assigned
else
{
for(let it = 0; it < ans.length - 1; it++)
{
document.write(ans[it][0] + "->" + ans[it][1] + "</br>");
}
}
}
// Function to create graph
function createGraph(Edges, adj, M)
{
// Traverse the Edges
for(let i = 0; i < M; i++)
{
let u = Edges[i][0];
let v = Edges[i][1];
// Push the edges in an
// adjacency list
adj[u].push(v);
adj[v].push(u);
}
}
// N vertices and M Edges
let N = 5, M = 6;
let Edges = [ [ 0, 1 ], [ 0, 2 ],
[ 1, 2 ], [ 1, 4 ],
[ 2, 3 ], [ 3, 4 ] ];
// To create Adjacency List
let adj = [];
ans = [];
for(let i = 0; i < N; i++)
adj.push([]);
// Create an undirected graph
createGraph(Edges, adj, M);
// Function Call
convert(adj, N);
// This code is contributed by suresh07.
</script>
Producción:
0->1 2->0 4->1 3->4 2->3 1->2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA