拓扑排序-白红宇

拓扑排序

阅读量：5162 次

发布时间：2019-06-13

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

貌似从来没有敲过拓扑排序的板子，，，记录一下

拓扑排序就是对DAG有向无环图中的边u->v,要求排序出一个点的序列，满足u在v的前面，，

算法的思路是不停的将入度为零的点u放到前面，并且对u能到达的所有点v的入度递减，，循环处理所有的点即可，，期间将所有入度为零的点放在一个队列中，，

这道题要求对于多种可能的排序输出字典序最小的那种，，用优先队列代替原来的队列就行了，，

注意杭电上不能用万能头文件，而且优先队列的由小到大的写法 priority_queue<int, vector<int>, greater<int> > q;,头文件要加 #include <queue> 和 #include <functional> （一直不知道，，，233，，，

还有好久不练忘记多组数据要记得清零那些数组，，

代码：

//#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define aaa cout<<233<
            
              '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}//red_book//l[maxn]为最后排序的结果vector
             
               g[maxn];int du[maxn], n, m, l[maxn];bool toposort(){ memset(du, 0, sizeof du); for(int i = 1; i <= n; ++i) for(int j = 0; j < g[i].size(); ++j) ++du[g[i][j]]; int tot = 0; priority_queue

, greater

> q;//按字典序最小的排序时 //queue

q; for(int i = 1; i <= n; ++i) if(!du[i]) q.push(i); while(!q.empty()) { int x = q.top(); q.pop(); l[tot++] = x; for(int j = 0; j < g[x].size(); ++j) { int t = g[x][j]; --du[t]; if(!du[t])q.push(t); } } if(tot == n)return 1; else return 0;}int main(){// freopen("233.in" , "r" , stdin);// freopen("233.out" , "w" , stdout);// ios_base::sync_with_stdio(0);// cin.tie(0);cout.tie(0); int u, v; while(scanf("%d%d", &n, &m) != EOF) { for(int i = 0; i <= n; ++i)g[i].clear(); for(int i = 0; i <= n; ++i)du[i] = l[i] = 0; for(int i = 1; i <= m; ++i) { scanf("%d%d", &u, &v); g[u].push_back(v); } toposort(); for(int i = 0; i < n - 1; ++i)printf("%d ", l[i]);printf("%d\n", l[n - 1]); } return 0;}

(end)

转载于:https://www.cnblogs.com/31415926535x/p/10367483.html

你可能感兴趣的文章