题目描述：
一张图， $n$ 个点， $m$ 条边，其中边 $[a_i,b_i]$ 表示 $b_i\rightarrow a_i$ 有一条有向边。对该图拓扑排序，如果有环则返回空，无环则返回拓扑排序的结果。
数据范围：
$1\le n \le 2000;0\le m \le \frac{n \times(n - 1)}{2}$
题解：
bfs版本：
拓扑排序bfs版已经非常熟悉了，统计有向图的入度，入度为 $0$ 的加入队列。然后出队，加入答案，将邻接点的入度减 $1$ ，最终如果得到的点的个数不等于 $n$ ，说明存在环。
dfs版本：
dfs版需要检测环，可以使用 $vis[i]=0/1/2$ 表示未遍历，遍历中，遍历后。也可以使用两个数组 $onpath$ 表示遍历中， $vis$ 表示未遍历。后序遍历的位置将当前点加入答案，因为后序遍历时，当前点的出边已经全部遍历过了，当前点比自己的孩子入答案晚。因此翻转之后就是正确的拓扑排序的结果。
代码：
bfs版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
{
vector<vector<int>> g(numCourses);
vector<int> indeg(numCourses, 0);
int m = prerequisites.size();
for (int i = 0; i < m; ++i)
{
g[prerequisites[i][1]].emplace_back(prerequisites[i][0]);
++indeg[prerequisites[i][0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
{
if (!indeg[i])
q.push(i);
}
vector<int> ans;
while (q.size())
{
int u = q.front();
ans.emplace_back(u);
q.pop();
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
indeg[v]--;
if (!indeg[v])
q.push(v);
}
}
if (ans.size() != numCourses)
return {};
return ans;
}
};
|
dfs版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<bool> vis;
vector<bool> onpath;
vector<vector<int>> g;
vector<int> tmp;
bool ans = true;
void dfs(int u)
{
if (!ans)
return;
if (onpath[u])
{
ans = false;
return;
}
if (vis[u])
return;
onpath[u] = true;
vis[u] = true;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
dfs(v);
}
onpath[u] = false;
tmp.emplace_back(u);
}
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
{
vis.resize(numCourses);
onpath.resize(numCourses);
g.resize(numCourses);
for (int i = 0; i < prerequisites.size(); ++i)
{
g[prerequisites[i][1]].emplace_back(prerequisites[i][0]);
}
for (int i = 0; i < numCourses; ++i)
{
if (vis[i])
continue;
dfs(i);
}
if (!ans)
return {};
else
{
reverse(tmp.begin(), tmp.end());
return tmp;
}
}
};
|