สมมติว่ามี n โหนดติดป้าย 0 ถึง n-1 และรายการขอบแบบไม่มีทิศทาง [u,v] เราต้องกำหนดฟังก์ชันตรวจสอบว่าขอบเหล่านี้สร้าง valid tree ได้หรือไม่
เช่น ถ้าอินพุทเป็น n = 5, และ edges = [[0,1], [0,2], [0,3], [1,4]] ผลลัพธ์จะเป็น true
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดฟังก์ชัน dfs() รับ node, par, graph, อาร์เรย์ visited
ถ้า visited[node] เท่ากับ 1 แล้ว −
คืนค่า true
ถ้า visited[node] เท่ากับ 2 แล้ว −
คืนค่า false
visited[node] := 2
ret := true
ลูป i := 0 ถึงขนาดของ graph[node]-1 ทำ −
ถ้า graph[node][i] ไม่เท่ากับ par แล้ว −
ret := ret AND dfs(graph[node][i], node, graph, visited)
visited[node] := 1
คืนค่า ret
จากเมธอดหลักทำดังนี้ −
กำหนดอาร์เรย์ visited ขนาด n เติม 0
กำหนดรายการรายการ graph ขนาด n
ลูป i := 0 ถึงขนาดของ edges-1 ทำ −
u := edges[i][0], v := edges[i][1]
แทรก v ที่ท้ายของ graph[u]
แทรก u ที่ท้ายของ graph[v]
ถ้า dfs(0, -1, graph, visited) เป็น false แล้ว −
คืนค่า false
ลูป i := 0 ถึง n-1 ทำ −
ถ้า visited[i] เป็นศูนย์ แล้ว −
คืนค่า false
คืนค่า true
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#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
