拓扑排序-白红宇的个人博客

拓扑排序

发布日期：2021-05-06 17:49:01 浏览次数：9 分类：技术文章

本文共 2616 字，大约阅读时间需要 8 分钟。

拓扑排序的适用范围：

有向无环图（DAG）

最简单的拓扑排序入门

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int mod = 1e6 + 10;const int N = 3e7+10;const int inf = 0x7fffffff;int n, m; int in[50];vector 
           
             e[50], ans;int main(){ set
            
              k; char s[5]; while(~scanf("%s", s)) { int x = s[0]-'A', y = s[2]-'A'; k.insert(x);k.insert(y); if(s[1]=='>') { in[y]++; e[x].push_back(y); } else { in[x]++; e[y].push_back(x); } } priority_queue

, greater

> q; // 因为要输出字典序最小的答案，所以用优先队列维护 for(int i = 0; i <= 30; ++i) { if(!in[i] && k.count(i)) q.push(i); } while(!q.empty()) { int now = q.top(); q.pop(); ans.push_back(now); for(int i = 0; i < e[now].size(); ++i) { int tmp = e[now][i]; in[tmp]--; if(!in[tmp]) q.push(tmp); } } if(ans.size() == k.size()) { for(int i = 0; i < ans.size(); ++i) printf("%c",ans[i] + 'A'); cout << endl; } else cout << "No Answer!\n"; return 0;}

难度+++

小的头部不一定排在前面，但是大的尾部一定排在后面

所以我们逆向思考，按照编号大，后出队（入度大的）的的在前的入队，最后逆序输出。

反向拓扑排序+优先队列

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int mod = 1e6 + 10;const int N = 1e5 + 10;const int inf = 0x7fffffff;int n, m; int in[N];vector 
           
             e[N], ans;void intt(){ for(int i = 0; i <= n; ++i) { e[i].clear();in[i] = 0; } ans.clear();}void work(){ cin >> n >> m; int a, b; intt(); for(int i = 1; i <= m; ++i) { scanf("%d %d", &a, &b); in[a]++; e[b].push_back(a); } priority_queue
            
              q;// 维护编号大的在前 for(int i = 1; i <= n; ++i) if(!in[i]) q.push(i); while(!q.empty()) { int now = q.top(); q.pop(); ans.push_back(now); for(int i = 0; i < e[now].size(); ++i) { int tmp = e[now][i]; in[tmp]--; if(!in[tmp]) q.push(tmp); } } for(int i = ans.size() - 1; i >= 0; --i) printf("%d%c",ans[i], i == 0 ? '\n' : ' ');}int main(){ int t; cin >> t; while(t--) work(); return 0;}/*19 66 44 13 99 25 77 8*/

拓扑排序 + dp

#include
   
    using namespace std;const int N = 2e5 + 9;int n, m;vector 
    
      v[N];int dis[N], in[N];queue 
     
       q;// 因为不需要用队列维护什么顺序，所以普通队列即可int main(){   	cin >> n >> m;	for(int i = 1; i <= m; ++i)	{   		int a, b;		scanf("%d %d", &a, &b);		in[b]++;		v[a].push_back(b);	}	for(int i = 1; i <= n; ++i)	{   		if(!in[i])	q.push(i);		dis[i] = 1;	}	while(!q.empty())	{   		int now = q.front();		q.pop();		for(int i = 0 ; i < v[now].size(); ++i)		{   			int tmp = v[now][i];			in[tmp]--;			if(!in[tmp])			{   				q.push(tmp);				dis[tmp] = dis[now] + 1;			}		}	}	for(int i = 1; i <= n; ++i)		cout << dis[i] << endl;	return 0;}

上一篇：sdnu oj 1301

下一篇：C++ STL

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章