循环依赖 #include #include #include #include using namespace std; const int MAX = 10000; vector graph[MAX]; int visited[MAX] = {0}; int inStack[MAX] = {0}; stack stk; vector result; bool dfs(int u) { if (visited[u] == 1) { if (!stk.empty() && inStack[u] == 1) { while (!stk.empty() && stk.top() != u) { result.push_back(stk.top()); stk.pop(); } result.push_back(u); stk.pop(); return true; } else { return false; } } visited[u] = 1; stk.push(u); inStack[u] = 1; for (int v : graph[u]) { if (dfs(v)) { return true; } } inStack[u] = 0; stk.pop(); return false; } int main() { int n; cin >> n; for (int i = 0; i < MAX; i++) { graph[i].clear(); } for (int i = 0; i < n; i++) { int k; cin >> k; int a; cin >> a; for (int j = 0; j < k - 1; j++) { int b; cin >> b; graph[a].push_back(b); } } for (int i = 1; i < MAX; i++) { if (visited[i] == 0) { if (dfs(i)) { break; } } } if (!result.empty()) { reverse(result.begin(), result.end()); int minValue = *min_element(result.begin(), result.end()); int index = find(result.begin(), result.end(), minValue) - result.begin(); vector finalResult(result.begin() + index, result.end()); finalResult.insert(finalResult.end(), result.begin(), result.begin() + index + 1); for (int node : finalResult) { cout << node << " "; } } return 0; } // vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。

全站热榜