原文:
给定由值为【0，n–1】的节点组成的有向 g n 节点和 e 边，以及表示顶点 u 和 v 之间的
示例:
输入: n = 4，e = 4，边[][2] = { {0，2}，{0，1}，{2，3}，{3，0} } 输出:1 t6】解释:t8】
从上面给定的图中，节点 0 -> 2 -> 3 -> 0 之间存在一个循环。 任何周期都不发生的节点为 1。 因此，打印 1。
输入: n = 6，e = 7，edges[][2] = { {0，1}，{0，2}，{1，3}，{2，1}，{2，5}，{3，0}，{4，5 } } t3】输出:4 5 t6】解释:t8】
从上面给定的图中，节点之间存在循环: 1) 0 - > 1 - > 3 - > 0。 2)0->2->1->3->0。 任何周期都不发生的节点是 4 和 5。 因此，打印 4 和 5。
天真方法:最简单的方法是中的一个循环，并且只打印那些不属于给定图中任何循环的节点。 时间复杂度: o(v * (v e))，其中 v 为顶点数，e 为边数。 辅助空间: o(v)
高效方法:为了优化上述方法，其思想是每当给定图中有任何周期时，将中间节点存储为访问周期节点。要实现这一部分，请使用辅助数组循环数组[] ，该数组将在执行 时存储中间循环节点。以下是步骤:
- 初始化一个大小为 n 的辅助数组 cyclepart[] ，这样如果 cyclepart[i] = 0 ，那么 i th 节点在任何循环中都不存在。
- 初始化一个大小为 n 的辅助数组 recstack[] ，这样它将通过将被访问节点标记为 true 来将该节点存储在堆栈中。
- 对每个未访问的节点在给定的图上执行 dfs 遍历，并执行以下操作:
- 现在在给定的图中找到一个循环，每当找到一个循环时，将循环中的节点标记为真，因为该节点是循环的一部分。
- 如果任何节点在调用中被访问并且是 recstack【节点】也为真，则该节点是循环的一部分，然后将该节点标记为真。
- 执行 dfs 遍历后，遍历数组 循环【】并打印所有标记为 false 的节点，因为这些节点不是任何循环的一部分。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
class graph {
// no. of vertices
int v;
// stores the adjacency list
list* adj;
bool printnodesnotincycleutil(
int v, bool visited[], bool* rs,
bool* cyclepart);
public:
// constructor
graph(int v);
// member functions
void addedge(int v, int w);
void printnodesnotincycle();
};
// function to initialize the graph
graph::graph(int v)
{
this->v = v;
adj = new list[v];
}
// function that adds directed edges
// between node v with node w
void graph::addedge(int v, int w)
{
adj[v].push_back(w);
}
// function to perform dfs traversal
// and return true if current node v
// formes cycle
bool graph::printnodesnotincycleutil(
int v, bool visited[],
bool* recstack, bool* cyclepart)
{
// if node v is unvisited
if (visited[v] == false) {
// mark the current node as
// visited and part of
// recursion stack
visited[v] = true;
recstack[v] = true;
// traverse the adjacency
// list of current node v
for (auto& child : adj[v]) {
// if child node is unvisited
if (!visited[child]
&& printnodesnotincycleutil(
child, visited,
recstack, cyclepart)) {
// if child node is a part
// of cycle node
cyclepart[child] = 1;
return true;
}
// if child node is visited
else if (recstack[child]) {
cyclepart[child] = 1;
return true;
}
}
}
// remove vertex from recursion stack
recstack[v] = false;
return false;
}
// function that print the nodes for
// the given directed graph that are
// not present in any cycle
void graph::printnodesnotincycle()
{
// stores the visited node
bool* visited = new bool[v];
// stores nodes in recursion stack
bool* recstack = new bool[v];
// stores the nodes that are
// part of any cycle
bool* cyclepart = new bool[v];
for (int i = 0; i < v; i ) {
visited[i] = false;
recstack[i] = false;
cyclepart[i] = false;
}
// traverse each node
for (int i = 0; i < v; i ) {
// if current node is unvisited
if (!visited[i]) {
// perform dfs traversal
if (printnodesnotincycleutil(
i, visited, recstack,
cyclepart)) {
// mark as cycle node
// if it return true
cyclepart[i] = 1;
}
}
}
// traverse the cyclepart[]
for (int i = 0; i < v; i ) {
// if node i is not a part
// of any cycle
if (cyclepart[i] == 0) {
cout << i << " ";
}
}
}
// function that print the nodes for
// the given directed graph that are
// not present in any cycle
void solve(int n, int e,
int edges[][2])
{
// initialize the graph g
graph g(n);
// create a directed graph
for (int i = 0; i < e; i ) {
g.addedge(edges[i][0],
edges[i][1]);
}
// function call
g.printnodesnotincycle();
}
// driver code
int main()
{
// given number of nodes
int n = 6;
// given edges
int e = 7;
int edges[][2] = { { 0, 1 }, { 0, 2 },
{ 1, 3 }, { 2, 1 },
{ 2, 5 }, { 3, 0 },
{ 4, 5 } };
// function call
solve(n, e, edges);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for above approach
import java.util.*;
import java.lang.*;
class gfg
{
static arraylist> adj;
static int v;
// function to perform dfs traversal
// and return true if current node v
// formes cycle
static boolean printnodesnotincycleutil(
int v, boolean visited[],
boolean[] recstack, boolean[] cyclepart)
{
// if node v is unvisited
if (visited[v] == false)
{
// mark the current node as
// visited and part of
// recursion stack
visited[v] = true;
recstack[v] = true;
// traverse the adjacency
// list of current node v
for (integer child : adj.get(v))
{
// if child node is unvisited
if (!visited[child]
&& printnodesnotincycleutil(
child, visited,
recstack, cyclepart))
{
// if child node is a part
// of cycle node
cyclepart[child] = true;
return true;
}
// if child node is visited
else if (recstack[child])
{
cyclepart[child] = true;
return true;
}
}
}
// remove vertex from recursion stack
recstack[v] = false;
return false;
}
static void printnodesnotincycle()
{
// stores the visited node
boolean[] visited = new boolean[v];
// stores nodes in recursion stack
boolean[] recstack = new boolean[v];
// stores the nodes that are
// part of any cycle
boolean[] cyclepart = new boolean[v];
// traverse each node
for (int i = 0; i < v; i )
{
// if current node is unvisited
if (!visited[i])
{
// perform dfs traversal
if (printnodesnotincycleutil(
i, visited, recstack,
cyclepart)) {
// mark as cycle node
// if it return true
cyclepart[i] = true;
}
}
}
// traverse the cyclepart[]
for (int i = 0; i < v; i )
{
// if node i is not a part
// of any cycle
if (!cyclepart[i])
{
system.out.print(i " ");
}
}
}
// function that print the nodes for
// the given directed graph that are
// not present in any cycle
static void solve(int n, int e,
int edges[][])
{
adj = new arraylist<>();
for(int i = 0; i < n; i )
adj.add(new arraylist<>());
// create a directed graph
for (int i = 0; i < e; i )
{
adj.get(edges[i][0]).add(edges[i][1]);
}
// function call
printnodesnotincycle();
}
// driver function
public static void main (string[] args)
{
// given number of nodes
v = 6;
// given edges
int e = 7;
int edges[][] = { { 0, 1 }, { 0, 2 },
{ 1, 3 }, { 2, 1 },
{ 2, 5 }, { 3, 0 },
{ 4, 5 } };
// function call
solve(v, e, edges);
}
}
// this code is contributed by offbeat
python 3
# python3 program for the above approach
class graph:
# function to initialize the graph
def __init__(self, v):
self.v = v
self.adj = [[] for i in range(self.v)]
# function that adds directed edges
# between node v with node w
def addedge(self, v, w):
self.adj[v].append(w);
# function to perform dfs traversal
# and return true if current node v
# formes cycle
def printnodesnotincycleutil(self, v, visited,recstack, cyclepart):
# if node v is unvisited
if (visited[v] == false):
# mark the current node as
# visited and part of
# recursion stack
visited[v] = true;
recstack[v] = true;
# traverse the adjacency
# list of current node v
for child in self.adj[v]:
# if child node is unvisited
if (not visited[child] and self.printnodesnotincycleutil(child, visited,recstack, cyclepart)):
# if child node is a part
# of cycle node
cyclepart[child] = 1;
return true;
# if child node is visited
elif (recstack[child]):
cyclepart[child] = 1;
return true;
# remove vertex from recursion stack
recstack[v] = false;
return false;
# function that print the nodes for
# the given directed graph that are
# not present in any cycle
def printnodesnotincycle(self):
# stores the visited node
visited = [false for i in range(self.v)];
# stores nodes in recursion stack
recstack = [false for i in range(self.v)];
# stores the nodes that are
# part of any cycle
cyclepart = [false for i in range(self.v)]
# traverse each node
for i in range(self.v):
# if current node is unvisited
if (not visited[i]):
# perform dfs traversal
if(self.printnodesnotincycleutil(
i, visited, recstack,
cyclepart)):
# mark as cycle node
# if it return true
cyclepart[i] = 1;
# traverse the cyclepart[]
for i in range(self.v):
# if node i is not a part
# of any cycle
if (cyclepart[i] == 0) :
print(i,end=' ')
# function that print the nodes for
# the given directed graph that are
# not present in any cycle
def solve( n, e, edges):
# initialize the graph g
g = graph(n);
# create a directed graph
for i in range(e):
g.addedge(edges[i][0],
edges[i][1]);
# function call
g.printnodesnotincycle();
# driver code
if __name__=='__main__':
# given number of nodes
n = 6;
# given edges
e = 7;
edges = [ [ 0, 1 ], [ 0, 2 ],
[ 1, 3 ], [ 2, 1 ],
[ 2, 5 ], [ 3, 0 ],
[ 4, 5 ] ];
# function call
solve(n, e, edges);
# this code is contributed by rutvik_56
output:
4 5
时间复杂度: o(v e) 空间复杂度: o(v)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
