แผนภูมิต้นไม้ที่ถูกต้องใน C++

สมมติว่าเรามีโหนด n โหนดซึ่งมีป้ายกำกับตั้งแต่ 0 ถึง n-1 และรายการขอบที่ไม่มีทิศทาง [u,v] เราต้องกำหนดฟังก์ชันเพื่อตรวจสอบว่าขอบเหล่านี้เป็นต้นไม้ที่ถูกต้องหรือไม่

ดังนั้น หากอินพุตเป็น n =5 และ edge =[[0,1], [0,2], [0,3], [1,4]] ผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด พาร์ กราฟ และอาร์เรย์อื่นที่เรียกว่า เยี่ยมชมแล้ว

• ถ้าเยี่ยมชม[โหนด] เหมือนกับ 1 แล้ว −

  • คืนความจริง

• ถ้าเยี่ยมชม[โหนด] เหมือนกับ 2 แล้ว −

  • คืนค่าเท็จ

• เยี่ยมชม[โหนด] :=2

• ret :=จริง

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[โหนด] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้ากราฟ[node, i] ไม่เท่ากับพาร์ −

    • ret :=ret และ dfs(กราฟ[โหนด, i], โหนด, กราฟ, เข้าชมแล้ว)

• เยี่ยมชม[โหนด] :=1

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดอาร์เรย์ที่เข้าชมขนาด n และเติมค่านี้ด้วย 0

• กำหนดรายการที่เรียกว่ากราฟขนาด n

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดขอบ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • u :=edge[i, 0], v :=Edge[i, 1]

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้ายกราฟ[v]

• ถ้า dfs(0, -1, กราฟ, เข้าชม) เป็นเท็จ −

  • คืนค่าเท็จ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้าไปเยี่ยม[i] จะเป็นศูนย์ ดังนั้น −

    • คืนค่าเท็จ

• คืนความจริง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool dfs(int node, int par, vector <int< graph[], vector <int<& visited){
      if (visited[node] == 1)
         return true;
      if (visited[node] == 2)
         return false;
      visited[node] = 2;
      bool ret = true;
      for (int i = 0; i < graph[node].size(); i++) {
         if (graph[node][i] != par)
            ret &= dfs(graph[node][i], node, graph, visited);
      }
      visited[node] = 1;
      return ret;
   }
   bool validTree(int n, vector<vector<int<>& edges) {
      vector<int< visited(n, 0);
      vector<int< graph[n];
      for (int i = 0; i < edges.size(); i++) {
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      if (!dfs(0, -1, graph, visited))
         return false;
      for (int i = 0; i < n; i++) {
         if (!visited[i])
            return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,1},{0,2},{0,3},{1,4}};
   cout << (ob.validTree(5,v));
}

อินพุต

5, {{0,1},{0,2},{0,3},{1,4}}

ผลลัพธ์

1