반응형
https://leetcode.com/problems/minimum-height-trees/description/
위상정렬을 이용하여 풀 수 있었습니다.
주어진 그래프는 양방향이므로, indegree가 1인 노드들부터 순회할 때, 마지막 순번의 노드들이 MHT의 root가 됩니다.
class Solution {
public:
vector<int> graph[20000];
int ind[20000] = {0};
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if(n == 1) return {0};
for(auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
ind[e[0]]++;
ind[e[1]]++;
}
queue<int> q;
for(int i=0; i<n; i++) {
if(ind[i] == 1) {
q.push(i);
}
}
vector<int> res;
while(!q.empty()) {
res.clear();
int sz = q.size();
while(sz--) {
int node = q.front(); q.pop();
res.push_back(node);
for(int nxt : graph[node]) {
if(--ind[nxt] == 1) {
q.push(nxt);
}
}
}
}
return res;
}
};
반응형
'Algorithm' 카테고리의 다른 글
LeetCode 2997. Minimum Number of Operations to Make Array XOR Equal to K (0) | 2024.04.29 |
---|---|
LeetCode 752. Open the Lock (0) | 2024.04.29 |
LeetCode 1971. Find if Path Exists in Graph (0) | 2024.04.21 |
LeetCode 1992. Find All Groups of Farmland (1) | 2024.04.20 |
LeetCode 200. Number of Islands (0) | 2024.04.20 |