ผลคูณความยาวของทุกไซเคิลในกราฟแบบไม่มีทิศทางใน 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 และเรียกใช้เพื่อเดินทางโหนดโดยการระบายสี
• โหนดจะถูกทำเครื่องหมายว่าเยี่ยมชมครบถ้วนหรือบางส่วน
• โหนดที่เยี่ยมชมครบถ้วนไม่ต้องเยี่ยมชมอีก และไม่ต้องเก็บข้อมูล ในขณะที่โหนดที่เยี่ยมชมบางส่วนต้องเก็บเพราะจะถูกเยี่ยมชมอีกครั้ง
• พิมพ์ผลลัพธ์

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศฟังก์ชันเดินทางกราฟด้วยวิธี DFS
  void DFS(int i, int j, int color[], int highlight[], int parent[], int& number)
  ถ้า color[i] == 2
    คืนค่า
  จบถ้า
  ถ้า color[i] == 1
    ตั้งค่า number++
    ประกาศและตั้งค่า int temp = j
    ตั้งค่า highlight[temp] = number
    วนลูป While temp != i
      ตั้งค่า temp = parent[temp]
      ตั้งค่า highlight[temp] = number
    จบวน
    คืนค่า
  จบถ้า
  ตั้งค่า parent[i] = j
  ตั้งค่า color[i] = 1
  สำหรับ int k : graph[i]
    ถ้า k == parent[i]
      ข้าม
    จบถ้า
    เรียก DFS(k, i, color, highlight, parent, number)
  จบสำหรับ
  ตั้งค่า color[i] = 2
ขั้นตอน 2 → ประกาศฟังก์ชันหาผลคูณโหนดในไซเคิล
  int product(int edge, int highlight[], int& number)
  เรียก unordered_map<int, int> mp
  วนลูป For i = 1 ถึง edge และ i++
    ถ้า (highlight[i] != 0)
      ตั้งค่า mp[highlight[i]]++
    จบถ้า
  จบวน
  ประกาศและตั้งค่า int temp = 1
  วนลูป For i = 1 ถึง number และ i++
    ตั้งค่า temp = temp * mp[i]
  จบวน
  ถ้า number == 0
    ตั้งค่า temp = 0
  จบถ้า
  คืนค่า temp
ขั้นตอน 3 → ใน main()
  เรียกฟังก์ชัน insert(1, 2) เพื่อแทรกโหนด
  ประกาศ int color[size], parent[size]
  ประกาศ int highlight[size]
  ประกาศและตั้งค่า int number = 0
  ประกาศและตั้งค่า int edge = 10
  เรียก DFS(1, 0, color, highlight, parent, number)
  เรียกฟังก์ชันพิมพ์ product(edge, highlight, number)
หยุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector<int> graph[size];
// ฟังก์ชันเดินทางกราฟด้วยวิธี DFS
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
  // สำหรับโหนดที่เดินทางแล้ว
  if (color[i] == 2) {
    return;
  }
  // ยังไม่ได้เยี่ยมชมครบ
  if (color[i] == 1) {
    number++;
    int temp = j;
    highlight[temp] = number;
    // สำหรับการย้อนกลับโหนด
    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;
}
// ฟังก์ชันแทรกขอบไปยังกราฟ
void insert(int u, int v) {
  graph[u].push_back(v);
  graph[v].push_back(u);
}
// หาผลคูณโหนดในไซเคิล
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() {
  // สำหรับแทรกโหนดในกราฟ
  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);
  // ฟังก์ชันพิมพ์ไซเคิล
  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