概念

  • 拓扑排序(topological sort): 有向无环图(DAG)中,若存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面
  • 我们可以将偏序关系定义为有向边,然后对满足一定排序关系的序列进行拓扑排序,注意其可能有多种

拓扑排序主要有两种写法

DFS

每次选一个未访问的节点,然后将其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
vector<int> G[maxn];
int vis[maxn];
int topo[maxn],t;

bool dfs(int u)
{
vis[u]=-1; //正在访问
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(vis[v]<0) return false; //存在有向环
else if(!vis[v] && !dfs(v)) return false;
}
vis[u]=1;
topo[--t]=u;
}

bool topo_sort()
{
t=n;
memset(vis,0,sizeof vis);
for(int u=0; u<n; ++u)
if(!vis[u])
{
if(!dfs(u)) return false;
}
return true;
}

queue

每次选择一个入度为0的节点开始扩展,将其的出边全部删除,然后将此时入度为0的节点加入队列
使用优先队列能产生字典序最大的拓扑序
或者将优先队列操作符重载得到字典序最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool topo_sort()
{
queue<int> Q;
int cnt = 0,weiyi = 1,zero = 0;
for(int i=0;i<n;++i) if(!in[i]) Q.push(i),++zero;
if(zero > 1) weiyi = 0;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
--zero;
topo[cnt++] = u;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
in[v]--;
if(!in[v]) Q.push(v);
}
if(zero > 1) weiyi = 0;
}
return cnt == n;
}

题目