무방향 및 무가중 그래프가 입력으로 제공되며 주어진 작업에서 형성되는 주기의 곱을 찾아 결과를 표시하는 것이 작업입니다.
예시
입력
주어진 그림에서 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