概念:
一个有向无环图的拓扑序列是将图中的顶点排成一个线性序列, 使得对于图中任意一对顶点 u,v. 若存在边 <u,v>, 则线性序列中 u 出现在 v 之前.
算法实现:
(1) 若图中的点入度均大于 0 则不存在拓扑序列, 否则进行第二步
(2) 取一个入度为 0 的点 u 并将其放置序列末尾
(3) 删除点 u 以及从 u 伸出的边, 即将与 u 相连的点的入度减 1
(4) 若图中还存在顶点, 再从 (1) 开始
最基础的模板:
- #include <bits/stdc++.h>
- using namespace std;
- vector v[1010];
- queue q;
- int ans[1010];
- int n,m;
- void tuopu()
- {
- int cnt = 0;
- while(!q.empty())
- q.pop();
- for(int i=1;i<=n;i++)
- if(in[i] == 0)
- q.push_back(i);
- while(!q.empty())
- {
- int k = q.front();
- ans[++cnt] = k;
- q.pop();
- for(int i=0;i<v[k].size();i++)
- {
- in[ v[k][i] ]--;
- if(in[ v[k][i] ] == 0)
- q.push_back(v[k][i]);
- }
- }
- for(int i=1;i<=cnt;i++)
- {
- cout<<ans[i]<<" ";
- }
- return ;
- }
- int main()
- {
- while(cin>>n>>m &&n)
- {
- for(int i=1;i<=n;i++)
- v[i].clear();
- memset(in,0,sizeof(in));
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y;
- v[x].push_back(y);
- in[y]++;
- }
- tuopu();
- }
- return 0;
- }
定向题目:
1. 有向图判环 HDU - 3342
- #include
- #include
- #include
- #include
- using namespace std;
- vector v[110];
- queue q;
- int in[110];
- int n,m,x,y;
- bool tuopu()
- {
- int cnt = 0;
- while(!q.empty())
- q.pop();
- for(int i=0;i<n;i++)
- if(in[i] == 0){
- q.push(i);
- cnt++;
- }
- while(!q.empty())
- {
- int k = q.front();
- q.pop();
- for(int i=0;i<v[k].size();i++)
- {
- in[ v[k][i] ]--;
- if(in[ v[k][i] ] == 0){
- q.push(v[k][i]);
- cnt++;
- }
- }
- }
- if(cnt != n)
- return false;
- return true;
- }
- int main()
- {
- while(cin>>n>>m &&n)
- {
- for(int i=0;i<n;i++)
- v[i].clear();
- memset(in,0,sizeof(in));
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y;
- v[x].push_back(y);
- in[y]++;
- }
- if(tuopu()){
- cout<<"YES"<<endl;
- }else{
- cout<<"NO"<<endl;
- }
- }
- return 0;
- }
2. 反向拓扑 深搜 HDU - 2647
- #include
- #include
- #include
- #include
- using namespace std;
- #define ll long long
- ll money = 0;
- vector v[10010];
- queue q;
- int in[10010];
- int ans[10010];
- int n,m,x,y;
- void tuopu()
- {
- int cnt = 0;
- while(!q.empty())
- q.pop();
- for(int i=1;i<=n;i++)
- if(in[i] == 0){
- q.push(i);
- }
- while(!q.empty())
- {
- int k = q.front();
- q.pop();
- cnt++;
- for(int i=0;i<v[k].size();i++)
- {
- in[ v[k][i] ]--;
- if(in[ v[k][i] ] == 0){
- q.push(v[k][i]);
- ans[v[k][i]] = max(ans[k]+1,ans[v[k][i]]);
- }
- }
- }
- if(cnt == n)
- {
- money = 888*n;
- for(int i=1;i<=n;i++)
- {
- money += ans[i];
- }
- cout<<money<<endl;
- }else{
- cout<<"-1"<<endl;
- }
- return ;
- }
- int main()
- {
- while(cin>>n>>m && n)
- {
- for(int i=1;i<=n;i++)
- v[i].clear();
- memset(in,0,sizeof(in));
- memset(ans,0,sizeof(ans));
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y;
- v[y].push_back(x);
- in[x]++;
- }
- tuopu();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3071213.html