图论-拓扑排序

学离散的偏序关系时的一个应用，

问题：小方准备组织一次演讲比赛，有如下环节（未排序）：

- 进行彩排

- 确定演讲主题

- 租借服装

- 确定比赛时间

- 确定比赛地点

- 确定参赛人员

- 申请经费

- 确定嘉宾人选

- 购买奖品，装饰物

- 比赛啦~

但是：

- 确定演讲主题之后才能确定比赛时间；

- 确定主题之后才能准备申请经费

- 在确定选手是否能参加之前先要确定比赛时间

- 购买何种装饰物需由比赛地点确定

- 只有当选手确定之后，才能去借服装，租场地和确定要邀请的嘉宾

- 如果申请经费没有成功，那么不能去购买奖品和装饰品

- 在彩排之前需要借服装和确定地点

- 比赛只有当嘉宾都邀请成功，已购买奖品而且彩排过才能进行

这些环节之间有一些约束关系，那么该怎么办呢;

画偏序关系的哈斯图形式（方案可能有多种）：

{

偏序关系：（自反性，反对称性，传递性）

哈斯图的画法：

1，删除自环；

2，具有传递性的，删掉可直达的

3，重组位置，使得有向的箭头指向正上方或斜上方。

}

拓扑排序（topologicalSorting）：

输入：偏序集（A,R）

输出：A的元素在<意义下“从小到大”逐一列出所形成的序列

1， B<- A,S<-R,List<-空

2， while|B|>0 do

2.1, 从B中选择一个极小元x加入队列list

2.2， B<- B- {x}

2.3， S<- S|B

3， return list

维基百科上关于Kahn算法的伪码描述：

L← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    foreach node m with an edge e from nto m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least onecycle)
else
    return L (a topologically sortedorder)

算法：（kahn）

对于一个有向无环图（DAG）来说：

1), 统计所有节点的入度，对于入度为0的节点就可以分离出来，然后将这个节点指向所有节点的入度减去1；

2), 重复1),知道所有的节点都被分离出来，拓扑排序结束。

3), 如果最后不存在入度为0的节点，那就说明图有环，无解。

注：对于入度为0的节点，则这个节点没有前驱，只要不是孤立节点，那么完成这个节点之后，对于它的所有后继节点来说，前驱结点就完成了一个，入度进行-1。

代码：（kahn）

bool toposort() {
    q = new queue();
    for (i = 0; i < n; i++)
        if (in_deg[i] == 0) q.push(i);
    ans = new vector();
    while (!q.empty()) {
        u = q.pop();
        ans.push_back(u);
        for each edge(u, v) {
            if (--in_deg[v] == 0) q.push(v);
        }
    }
    if (ans.size() == n) {
        for (i = 0; i < n; i++)
            std::cout << ans[i] << std::endl;
        return true;
    } else {
        return false;
    }
}

拓扑排序的阶过不唯一，所以一般会按某种要求进行输出，就需要用到优先队列，按字典序输出：

 1 vector<int> head[maxn],ans;
 2 int n,m,in[maxn];
 3 void topologicalsorting()
 4 {
 5     cin>>n>>m;
 6     for(int i=0; i<m; i++)
 7     {
 8         int u,v;
 9         scanf("%d%d",&u,&v);
10         head[u].push_back(v);
11         in[v]++;
12     }
13     priority_queue<int,vector<int>,greater<int> > q;
14     for(int i=1; i<=n; i++)
15     {
16         if(!in[i])
17         {
18             q.push(i);
19         }
20     }
21     while(q.empty()&&ans.size()<n)
22     {
23         int v=q.top();
24         q.pop();
25         ans.push_back(v);
26         for(int i=0; i<head[v].size(); i++)
27         {
28             in[head[v][i]]--;
29             if(!in[head[v][i]])
30              q.push(head[v][i]);
31         }
32     }
33     if(ans.size()==n)
34     {
35         //找到了排序
36     }
37     else
38     {
39         //图里有自环；
40     }
41     
42 }

算法：（DFS）

DFS版本：

 1 // dfs 版本
 2 bool dfs(int u) {
 3   c[u] = -1;
 4   for (int v = 0; v <= n; v++)
 5     if (G[u][v]) {
 6       if (c[v] < 0)
 7         return false;
 8       else if (!c[v])
 9         dfs(v);
10     }
11   c[u] = 1;
12   topo.push_back(u);
13   return true;
14 }
15 bool toposort() {
16   topo.clear();
17   memset(c, 0, sizeof(c));
18   for (int u = 0; u <= n; u++)
19     if (!c[u])
20       if (!dfs(u)) return false;
21   reverse(topo.begin(), topo.end());
22   return true;
23 }

考虑一个图，删掉某个入度为的节点之后，如果新图可以拓扑排序，那么原图一定也可以。反过来，如果原图可以拓扑排序，那么删掉后也可以。

练习：

题的类型：

正向：

1，判断自环问题，

2，输出拓扑排序

3，字典序输出拓扑排序(最小优先队列维护)

反向拓扑：(最大优先队列维护）

1，自己是一个编号的

2，给自己贴标签问题

1，判断自环问题：链接

题意：就裸拓扑排序，判断一下自环；

code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+10;
 4 vector<int> G[maxn];
 5 int in[maxn];
 6 int n,m;
 7 int sum;
 8 queue<int> q;
 9 int toposort()
10 {
11     while(!q.empty())
12      q.pop();
13     sum=0;
14     for(int i=1; i<=n; i++)
15      if(!in[i])
16       q.push(i);
17     while(!q.empty())
18     {
19         int v=q.front();
20         q.pop();
21         sum++;
22         for(int i=0; i<G[v].size(); i++)
23         {
24             in[G[v][i]]--;
25             if(!in[G[v][i]])
26              q.push(G[v][i]);
27         }
28     }
29     if(sum==n)
30      return 1;
31     else
32     {
33         return 0;
34     }
35     
36 }
37 int main()
38 {
39     int t;
40     cin>>t;
41     while(t--)
42     {
43         cin>>n>>m;
44         memset(G,0,sizeof(G));
45         memset(in,0,sizeof(in));
46         for(int i=1; i<=m; i++)
47         {
48             int u,v;
49             cin>>u>>v;
50             G[u].push_back(v);
51             in[v]++;
52         }
53         if(toposort())
54          cout<<"Correct"<<endl;
55         else
56         {
57             cout<<"Wrong"<<endl;
58         }
59         
60     }
61     //system("pause");
62     return 0;
63 }

2，同1，判断自环，注意范围变了，从0~n-1；（HDU3342）

code：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+10;
 4 vector<int> G[maxn];
 5 int in[maxn];
 6 int n,m;
 7 int sum;
 8 queue<int> q;
 9 int toposort()
10 {
11     while(!q.empty())
12      q.pop();
13     sum=0;
14     for(int i=0; i<n; i++)
15      if(!in[i])
16       q.push(i);
17     while(!q.empty())
18     {
19         int v=q.front();
20         q.pop();
21         sum++;
22         for(int i=0; i<G[v].size(); i++)
23         {
24             in[G[v][i]]--;
25             if(!in[G[v][i]])
26              q.push(G[v][i]);
27         }
28     }
29     if(sum==n)
30      return 1;
31     else
32     {
33         return 0;
34     }
35     
36 }
37 int main()
38 {
39     
40     while(cin>>n>>m)
41     {
42         if(!n&&!m)
43          break;
44         memset(G,0,sizeof(G));
45         memset(in,0,sizeof(in));
46         for(int i=1; i<=m; i++)
47         {
48             int u,v;
49             cin>>u>>v;
50             G[u].push_back(v);
51             in[v]++;
52         }
53         if(toposort())
54          cout<<"YES"<<endl;
55         else
56         {
57             cout<<"NO"<<endl;
58         }
59     }
60     system("pause");
61     return 0;
62 }

3，拓扑排序的应用；链接

题意：有n个节点，初始时，第k个节点上有一个病毒，病毒可以传递，问最终病毒的总和

题解：拓扑排序裸题，路过每个结点时加一下，即可(它的后继的病毒数，就等于后继本来的病毒数+它的病毒数，遍历完就可以）

code；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=142857;
 5 vector<int> G[maxn];
 6 int in[maxn];
 7 int a[maxn];
 8 queue<int> q;
 9 int n,m,k;
10 void toposort()
11 {
12     while(!q.empty()) q.pop();
13     for(int i=1; i<=n; i++)
14      if(!in[i])
15       q.push(i);
16     while(!q.empty())
17     {
18         int v=q.front();
19         q.pop();
20         for(int i=0; i<G[v].size(); i++)
21         {
22             in[G[v][i]]--;
23             if(!in[G[v][i]])
24              q.push(G[v][i]);
25             a[G[v][i]]=(a[G[v][i]]+a[v])%mod;
26         }
27     }
28 }
29 int main()
30 {
31     while(cin>>n>>m>>k)
32     {
33         int x;
34         for(int i=1; i<=k; i++)
35         {
36             cin>>x;
37             a[x]++;
38         }
39         for(int i=1; i<=m; i++)
40         {
41             int u,v;
42             cin>>u>>v;
43             G[u].push_back(v);
44             in[v]++;
45         }
46         toposort();
47         int sum=0;
48         for(int i=1; i<=n; i++)
49          sum=(sum+a[i])%mod;
50         cout<<sum<<endl;
51     }
52 }

4，拓扑排序+dp，skiing

题意：给你n个点，m条边的DAG，求一条最长路

题解：首先拓扑排序的中心思想不变，然后考虑一下最长路，思想就最短路的思想，dp[v]表示在从u（入度为0的点）开始到节点v的最长路径，

然后状态转移方程dp[v]=max(dp[v],dp[u]+w(u,v) )(最短路思想,想一下)最后max(dp[v])就是答案；

code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=142857;
vector<pair<int,int> > G[maxn];
int in[maxn];
int dp[maxn];
int n,m;
void toposort()
{
    queue<int> q;
    while(!q.empty()) q.pop();
    for(int i=1; i<=n; i++)
     if(!in[i])
      q.push(i);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++)
        {
            int edge=G[v][i].first;
            in[edge]--;
            if(!in[edge])
             q.push(edge);
          dp[edge]=max(dp[edge],dp[v]+G[v][i].second);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        //int n,m;
        cin>>n>>m;
        memset(in,0,sizeof(in));
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++) G[i].clear();
        for(int i=1; i<=m; i++)
        {
            int u,v,w;
          scanf("%d%d%d",&u,&v,&w );
            G[u].push_back(make_pair(v,w));
            in[v]++;
        }
        toposort();
        int ma=0;
        for(int i=1; i<=n; i++)
         ma=max(ma,dp[i]);
        cout<<ma<<endl;
    }
    return 0;
}

5,Almost Acyclic Graph 链接

题意：给一张图，可以删除一条边，问图可否构成没有自环的图

裸拓扑排序，对入度进行减一，判断一下即可；

code；

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 int in[maxn],deg[maxn];
 5 vector<int> G[maxn];
 6 int n,m;
 7 queue<int> q;
 8 int toposort()
 9 {
10   while(!q.empty()) q.pop();
11   for(int i=1; i<=n; i++)
12    if(!in[i])
13     q.push(i);
14   int sum=0;
15   while(!q.empty())
16   {
17     int v=q.front();
18     q.pop();
19     sum++;
20     for(int i=0; i<G[v].size(); i++)
21     {
22       in[G[v][i]]--;
23       if(!in[G[v][i]])
24        q.push(G[v][i]);
25     }
26   }
27   if(sum==n)
28    return 1;
29   else
30    return 0;
31 }
32 int main()
33 {
34   cin>>n>>m;
35   while(m--)
36   {
37     int u,v;
38     cin>>u>>v;
39     G[u].push_back(v);
40     in[v]++;
41     deg[v]++;
42   }
43   if(toposort()) cout<<"YES
";
44   else
45   {
46     int flag=0;
47     for(int i=1; i<=n; i++)
48     {
49       if(deg[i]>=1)
50        {
51          memcpy(in,deg,sizeof deg);
52          in[i]--;
53          if(toposort())
54           {
55             flag=1;
56             cout<<"YES
";
57             break;
58           }
59        }
60     }
61     if(!flag) cout<<"NO
";
62   }
63 }

6，AcWing1191家谱树

裸拓扑排序，

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int> G[maxn],ans;
int in[maxn];
int n;
queue<int> q;
void toposort()
{
    for(int i=1; i<=n; i++)
     if(!in[i])
      q.push(i);
     while(!q.empty())
     {
         int v=q.front();
         q.pop();
         ans.push_back(v);
         for(int i=0; i<G[v].size(); i++)
         {
             in[G[v][i]]--;
             if(!in[G[v][i]])
              q.push(G[v][i]);
         }
     }
     for(auto x:ans)
      cout<<x<<" ";
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int x;
        while(cin>>x)
        {
            if(!x)
             break;
            G[i].push_back(x);
            in[x]++;
        }
    }
    toposort();
}

7，确定比赛名次

回到刚开始的板子，拓扑排序+优先队列字典序输出

这个题要小的先输出，还是裸的拓扑排序

code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int in[maxn],deg[maxn];
vector<int> G[maxn];
int n,m;
priority_queue<int,vector<int>,greater<int> > q;
void toposort()
{
  while(!q.empty()) q.pop();
  vector<int> ans;
  for(int i=1; i<=n; i++)
   if(!in[i])
    q.push(i);
  while(!q.empty())
  {
    int v=q.top();
    q.pop();
    ans.push_back(v);
    for(int i=0; i<G[v].size(); i++)
    {
      in[G[v][i]]--;
      if(!in[G[v][i]]) q.push(G[v][i]);
    }
  }
  for(int i=0; i<ans.size(); i++)
   if(i!=n-1) printf("%d ",ans[i]);
   else printf("%d
",ans[i]);
}
int main()
{
  while(cin>>n>>m)
  {
    for(int i=0; i<=n; i++)
    {
      G[i].clear();
    }
    memset(in,0,sizeof(in));
    while(m--)
    {
      int u,v;
      cin>>u>>v;
      G[u].push_back(v);
      in[v]++;
    }
    toposort();
  }
}

8，逃生HDU4857

观察可以看出按上一个题的写法不对，那么考虑一下反向建边，然后跑一遍字典序最大的拓扑排序优先队列维护，然后倒序输出就可

code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int in[maxn],deg[maxn];
vector<int> G[maxn];
int n,m;
priority_queue<int> q;
void toposort()
{
  while(!q.empty()) q.pop();
  vector<int> ans;
  for(int i=1; i<=n; i++)
   if(!in[i])
    q.push(i);
  while(!q.empty())
  {
    int v=q.top();
    q.pop();
    ans.push_back(v);
    for(int i=0; i<G[v].size(); i++)
    {
      in[G[v][i]]--;
      if(!in[G[v][i]])
       q.push(G[v][i]);
    }
  }
  for(int i=n-1; i>=0; i--)
   if(i!=0) printf("%d ",ans[i]);
   else printf("%d
",ans[i]);
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
      G[i].clear();
    }
    memset(in,0,sizeof(in));
    while(m--)
    {
      int u,v;
      scanf("%d%d",&u,&v);
      G[v].push_back(u);
      in[u]++;
    }
    toposort();
  }
}

9，poj3678Labeling Balls

优先队列+反向拓扑

根据题的要求，要先保证1号球最轻，若我们由轻的向重的连边，然后我们依次有小到大每次把重量分给一个入度为0的点，那么在拓扑时我们面对多个入度为0的点，我们不知道该把最轻的分给谁才能以最快的速度找到1号（使1号入度为0），并把当前最轻的分给1号。所以我们要由重的向轻的连边，然后从大到小每次把一个重量分给一个入度为0的点。这样我们就不用急于探求最小号。我们只需要一直给最大号附最大值，尽量不给小号赋值，这样自然而然就会把轻的重量留给小号。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
std::vector<int> G[maxn];
int ans[maxn];
int n,m;
int in[maxn];
priority_queue<int> q;
void toposort()
{
  int sum=0;
  int cnt=n;
  while(!q.empty()) q.pop();
  for(int i=1; i<=n; i++)
  if(!in[i]) q.push(i);
  while(!q.empty())
  {
    int v=q.top();
    q.pop();
    ans[v]=cnt--;
    sum++;
    for(int i=0; i<G[v].size(); i++)
    {
      in[G[v][i]]--;
      if(!in[G[v][i]]) q.push(G[v][i]);
    }
  }
  if(sum==n)
  {
    for(int i=1; i<=n; i++)
     if(i==n) printf("%d
",ans[i]);
     else printf("%d ",ans[i]);
  }
  else
  printf("-1
");
}
void solve()
{
  cin>>n>>m;
  memset(in,0,sizeof(in));
  memset(ans,0,sizeof(ans));
  for(int i=1; i<=n; i++)
   G[i].clear();
  while(m--)
  {
    int u,v;
    cin>>u>>v;
    G[v].push_back(u);
    in[u]++;
  }
  toposort();
}
int main()
{
  int t;
  cin>>t;
  while(t--) solve();
  return 0;
}

View Code