拓扑排序 ( TopSort ) |
您所在的位置：网站首页 › 拓扑排序的规则 › 拓扑排序 ( TopSort ) |
|
拓扑排序
时间复杂度：O(n+m) 因每个结点只需加入队列一次，而每个结点加入队列前需要进行入度数量次的操作，因此时间复杂度为 O(n+m)。 无法排序？：当有 类似 0 → 1 ，且 1 → 0 ，或 1 → 2 ， 2 → 3 ，3 → 1 ，的时候，会形成一个环，导致上一个队列中的元素被移走后，没有入度为0的点，导致 while( ! q.empty ( ) ) 终止，cnt < n 核心算法 ： void TopSort() { for(int i = 1; i fir = q.front(); q.pop(); ans[++cnt] = fir; //cnt计数，遍历点的个数 for(int i=0; i for(int i = 1; i fir = q.front(); q.pop(); ans[++cnt] = fir; for(int i=0; i cin >> n; for(int i = 1; i v[i].push_back(x); inp[x]++; } } if(bfs()) { printf("%d",ans[1]); for(int i = 2 ; i if(inp[i] == 0) q.push(i); } while(!q.empty()) { qsize=q.size(); while(qsize--) //while代表一层 { fir = q.front(); q.pop(); cnt++; for(int i=0; i sum+=jishu; q.push(sec); } } } jishu++; //一层过后加一 } } int main() { while(~scanf("%d %d",&n,&m)) { memset(v,0,sizeof(v)); memset(ans,0,sizeof(ans)); memset(inp,0,sizeof(inp)); cnt=0; for(int i = 1; i v[y].push_back(x); inp[x]++; } } bfs(); if(cnt != n) printf("-1\n"); else printf("%d\n",888*n+sum); } return 0; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |