BFS搜拓扑序
前置知识
BFS层序遍历
针对有向图使用
可以判断有向图是否有环,生成拓扑序
若有环则无拓扑序 若tp.size() == n 则无环可走完
bfs的特殊应用
算法流程：
找到一个入度为0 的点 入队 然后出队后加入答案数组，然后不断层层扩展这个入度为0的点 没拓展一个点就删除该点的入度，最先被删为0的则加入答案 再出队 然后重复操作拓展
有向无环图一定至少存在一个入度度数为0 的点
反证
若所有点的入度都不是0 可以找到上一个点，若存在n个点
因为可以无穷无尽往上找下去. 必然可以找到n+1个点 由
抽屉原理 则必然找到有两个点是相同的，则说明有环
有向无环图不断删边删完之后肯定还是有向无环
需要注意的是一开始要开一个数组统计每个点的入度
考虑一个图，删掉某个入度为 
的节点之后，如果新图可以拓扑排序，那么原图一定也可以。反过来，如果原图可以拓扑排序，那么删掉后也可以
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
|
struct edge{
int v,w,next;
};
const int N = 114514;
int h[N];
edge e[N];
int idx = 0;
int n , m ;
void add(int u , int v, int w){
e[idx] = {v,w,h[u]};
h[u] = idx++;
}
int din[N];
vector<int> tp;
bool toposort(){
queue<int> q;
for(int i = 1;i<=n;++i) if(!din[i]) q.push(i);
while(q.size()){
int x = q.front();q.pop();
//出来的点就是入度为0的点
//而入度为0的点 说明没有点在前面
tp.pb(x);
//不断删边 谁最先为0 谁就在前面
for(int j = h[x];~j;j = e[j].next){
if(--din[e[j].v] == 0) q.push(e[j].v);
}
}
return tp.size() == n;
}
|
dfs 搜拓扑排序
只是作为一种思想 后序匈牙利算法铺垫
染色 三个状态 0 没遍历过 -1遍历过 1标记子连通块都没环 没问题直接入队
-1这个状态主要是检测是否有环和无环的
最后要反转 因为是你是从[1,n]开始搜点的. 是存点是自底向上。 要搜的拓扑序是从小到大
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
|
struct edge{
int v,next;
};
const int N = 114514;
int h[N];
edge e[N];
int idx = 0;
void add(int u , int v){
e[idx] = {v,h[u]};
h[u] = idx++;
}
int n , m ;
vector<int> tp;
int c[N];
bool dfs(int x){
c[x] = -1;
for(int i = h[x];~i;i = e[i].next){
int v = e[i].v;
if(c[v] < 0) return false;
else if(!c[v])
if(!dfs(v)) return false;
}
tp.pb(x);
c[x] = 1;
return true;
}
bool toposort(){
ms(c);
for(int i = 1;i<=n;++i){
if(!c[i])
if(!dfs(i)) return false;
}
reverse(tp.begin(),tp.end());
return true;
}
|
作业
该题最好学会拓扑和最短路判环再去做
https://www.luogu.com.cn/problem/P1347
若求字典序 可以用小根堆 复杂度上升 (有堆调整)
o(u +v) -> o(u+vlogv)
参考oiwiki