資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告