10-14 19:22 清华大学 市场 发布于江苏
关注
循环依赖
#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收割机，代码可能需要少量调试。
#include
#include
#include
#include
using namespace std;
const int MAX = 10000;
vector
int visited[MAX] = {0};
int inStack[MAX] = {0};
stack
vector
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.insert(finalResult.end(), result.begin(), result.begin() + index + 1);
for (int node : finalResult) {
cout << node << " ";
}
}
return 0;
}
// vx公众号关注TechGuide，专业生产offer收割机，代码可能需要少量调试。
全部评论
相关推荐
点赞 评论 收藏
分享
友塔游戏
| 校招
| 超多精选岗位
点赞 评论 收藏
分享
投递叠纸游戏等公司10个岗位 点赞 评论 收藏
分享