拓扑排序

1. bfs

vector<vector<int>> edges;
vector<int> indeg;
 
vector<int> topo() {
  vector<int> result;
  queue<int> q;
  for (int i = 0; i < indeg.size(); i++) {
    if (indeg[i] == 0) {
      q.push(i);
    }
  }
 
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    result.push_back(u);
    for (auto &v : edges[u]) {
      indeg[v]--;
      if (indeg[v] == 0) {
        q.push(v);
      }
    }
  }
 
  if (result.size() != indeg.size()) {
    return {};
  }
  return result;
}

bfs

2. dfs

vector<vector<int>> edges; // 邻接矩阵
vector<int> visited;
vector<int> result;
bool valid = true;
int n; // node size
 
void dfs(int u) {
  visited[u] = 1;
  for (auto &v : edges[u]) {
    if (visited[v] == 0) {
      dfs(v);
      if (!valid) {
        return;
      }
    } else if (visited[v] == 1) {
      valid = false;
      return;
    }
  }
  visited[u] = 2;
  result.push_back(u);
}
 
vector<int> topo() {
  for (int i = 0; i < n && valid; i++) {
    if (!visited[i]) {
      dfs(i);
    }
  }
	
  if (!valid) {
    return {};
  }
	
  reverse(result.begin(), result.end());
  return result;
}

dfs