class Solution {
vector<vector<int>>tmp;
vector<int>index;
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
tmp.resize(numCourses);
index.resize(numCourses);
for(auto&i:prerequisites){
tmp[i[1]].emplace_back(i[0]);
index[i[0]]++;
}
queue<int>que;
for(int i=0;i<numCourses;i++){
if(!index[i]) que.emplace(i);
}
int count=0;
while(!que.empty()){
count++;
int n=que.front();
que.pop();
for(int i:tmp[n]){
if(--index[i]==0) que.emplace(i);
}
}
return count>=numCourses;
}
};
class Solution {
vector<vector<int>>map;
vector<int>index;
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
map.resize(numCourses);
index.resize(numCourses);
for(auto& i:prerequisites){
map[i[1]].push_back(i[0]);
index[i[0]]++;
}
vector<int>res;
for(int i=0;i<numCourses;i++) if(!index[i]) res.push_back(i);
for(int i=0;i<res.size();i++){
for(int j:map[res[i]]){
if(!--index[j]){
res.push_back(j);
}
}
}
if(res.size()<numCourses) return {
};
return res;
}
};
从叶子节点不断向上拓扑，直到剩下至多2个节点作为根节点
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if(n==1) return {
0};
vector<vector<int>>tree(n);
vector<int>tmp(n);
for(auto& i:edges){
tree[i[0]].push_back(i[1]);
tree[i[1]].push_back(i[0]);
tmp[i[0]]++;
tmp[i[1]]++;
}
queue<int>que;
for(int i=0;i<n;i++){
if(tmp[i]==1) que.push(i);
}
for(int cur=n;cur>2;){
int size=que.size();
cur-=size;
while(size--){
int fr=que.front();
que.pop();
for(int i:tree[fr]){
if(--tmp[i]==1) que.push(i);
}
}
}
vector<int>res;
while(!que.empty()){
res.push_back(que.front());
que.pop();
}
return res;
}
};
