1

我是图论的新手，我是拓扑排序的新手。我所知道的是，要对某些任务进行拓扑排序，我必须对其运行 dfs，然后根据完成时间对顶点进行排序。嗯，我试过了。但不知何故，我得到了错误的答案。

假设一个图有 5 个顶点和 4 条边，边是 1->2、2->3、1->3、1->5，我的代码给出的答案是“4 1 5 2 3”应该给出“1 4 2 5 3”。我的代码有什么问题，或者我的拓扑排序有什么问题吗？

这是我的代码。

#include<iostream>
#include<vector>
#include<cstdio>
#include<stack>
#define MAX 100000

using namespace std;

vector<int> adj_list[MAX];
int f[MAX], d[MAX];//discovery time and finishing time
int color[MAX];
int time;
stack<int> stk;

void dfs(int vertex);
void dfs_visit(int u);

int main(void)
{
    freopen("input.txt", "r", stdin);
int vertex, edge;

//I am creating the adjacency list
cin >> vertex >> edge;
for(int i=1; i<=edge; i++)
{
    int n1, n2;
    cin >> n1 >> n2;
    adj_list[n1].push_back(n2);
}

//I am starting the depth-first-search
dfs(vertex);

return 0;
}

void dfs(int vertex)
{
    //If it's 0 then it means white
for(int i=1; i<=vertex; i++)
    if(color[i]==0) dfs_visit(i);


//Here I am printing the vertices
while(stk.size())
{
    cout << stk.top() << " ";
    stk.pop();
}
cout << endl;

return;
}

void dfs_visit(int u)
{
//If it's 1 then it means grey
color[u]=1;
d[u]=++time;

for(int i=0; i<adj_list[u].size(); i++)
{
    int v=adj_list[u][i];
    if(color[v]==0) dfs_visit(v);
}

//If it's 2 then it means black
color[u]=2;
f[u]=++time;

//I am inserting the vertex in the stack when I am finished, searching it
stk.push(u);
}
4

0 回答 0