数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究无向图中所有环的长度乘积（C++）
给定一个无向、无权图作为输入，任务是找到给定图中形成的环的乘积，并显示结果。
示例
输入
在给定的图中，有8个节点，其中5个节点形成一个环，包括1, 6, 3, 5, 8，其余节点不包含在环中。因此，环的长度为5（因为它包含5个节点），所以乘积为5。
在给定的图中，有12个节点，其中11个(5 + 6)节点形成环，包括1, 6, 3, 5, 8 和 9, 4, 10, 11, 22, 12，其余节点2不包含在环中。因此，环的长度为5 * 6 = 30。
下面程序中使用的算法如下：
- 输入形成环的节点
- 创建DFS函数并调用它来遍历顶点并对其着色
- 节点要么被标记为完全访问，要么被标记为部分访问
- 完全访问的节点不需要再次访问，因此不需要存储它；而部分访问的节点需要存储，因为它们会被再次访问。
- 打印结果
算法
Start Step 1-> declare function to traverse the graph using DFS approach void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) IF color[i] = 2 Return End IF color[i] = 1 Set number++ Declare and set int temp = j Set highlight[temp] = number Loop While temp != i Set temp = parent[temp] Set highlight[temp] = number End Return End Set parent[i] = j Set color[i] = 1 For int k : graph[i] IF k = parent[i] Continue End Call DFS(k, i, color, highlight, parent, number) End Set color[i] = 2 Step 2-> declare function to find product of nodes in cycle int product(int edge, int highlight[], int& number) call unordered_map<int, int> mp Loop For i = 1 and i <= edge and i++ IF (highlight[i] != 0) Set mp[highlight[i]]++ End End Declare and set int temp = 1 Loop For i = 1 and i <= number and i++ Set temp = temp * mp[i] End IF number = 0 Set temp = 0 End return temp Step 3-> In main() Call function as insert(1, 2) to insert a node Declare int color[size], parent[size] Declare int highlight[size] Declare and set int number = 0 Declare and set int edge = 10 Call DFS(1, 0, color, highlight, parent, number) Call print function as product(edge, highlight, number) Stop
示例
#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector<int> graph[size];
//function to traverse the graph using DFS approach
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
// for travered node
if (color[i] == 2) {
return;
}
//not completely visited
if (color[i] == 1) {
number++;
int temp = j;
highlight[temp] = number;
//for backtracking the vertex
while (temp != i) {
temp = parent[temp];
highlight[temp] = number;
}
return;
}
parent[i] = j;
color[i] = 1;
for (int k : graph[i]) {
if (k == parent[i]) {
continue;
}
DFS(k, i, color, highlight, parent, number);
}
color[i] = 2;
}
// function for inserting edges to graph
void insert(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
// Find product of nodes in cycle
int product(int edge, int highlight[], int& number) {
unordered_map<int, int> mp;
for (int i = 1; i <= edge; i++) {
if (highlight[i] != 0)
mp[highlight[i]]++;
}
int temp = 1;
for (int i = 1; i <= number; i++) {
temp = temp * mp[i];
}
if (number == 0)
temp = 0;
return temp;
}
int main() {
//for inserting a node in the graph
insert(1, 2);
insert(2, 3);
insert(3, 4);
insert(4, 6);
insert(4, 7);
insert(5, 6);
insert(3, 5);
insert(7, 8);
insert(6, 10);
insert(5, 9);
insert(10, 11);
int color[size], parent[size];
int highlight[size];
int number = 0;
int edge = 10;
DFS(1, 0, color, highlight, parent, number);
// function to print the cycles
cout<<"product of all the nodes in the cycle is :"<< product(edge, highlight, number);
return 0;
}输出
Product of all the nodes in the cycle is :4
更新于：2019年12月23日
190 次浏览
广告