传送门: 

 

拓扑排序(topological sort)简单题

 

自己代码的思路来自: ==> 

感谢n久前蔡大神扔给我这个链接2333333

 

1 #include 
     
       2 using namespace std; 3  4 const int MAXN = 111; 5 bool vis[MAXN]; 6 int G[MAXN][MAXN]; 7 int indegree[MAXN]; 8 int main(){ 9     int n, m;10     while(cin >> n >> m){11         if(n == 0 && m == 0) break;12         memset(vis, false, sizeof(vis));13         memset(G, 0, sizeof(G));14         memset(indegree, 0, sizeof(indegree));15         for(int i = 0; i < m; ++i){16             int a, b;17             cin >> a >> b;18             G[a][b] = 1;19             indegree[b] += 1;20         }21         queue
      
        q;22         while(!q.empty()) q.pop();23         for(int i = 1; i <= n; ++i)24             if(!indegree[i]) q.push(i);25         int total = n;26         while(!q.empty()){27             int cur = q.front();28             q.pop();29             cout << cur;30             if(--total) cout << " ";31             vis[cur] = true;32             for(int i = 1; i <= n; ++i){33                 if(G[cur][i]){34                     --indegree[i];35                     if(!indegree[i] && !vis[i])36                         q.push(i);37                 }38             }39         }40         cout << endl;41     }42     return 0;43 }
      
     

 

入门经典的思路：

1 #include 
     
       2 using namespace std; 3  4 const int MAXN = 111; 5 int n, m, t; 6 int vis[MAXN]; 7 int topo[MAXN]; 8 int G[MAXN][MAXN]; 9 10 bool dfs(int cur){11     //vis数组存储三个状态{-1, 0, 1}12     //-1 代表该点正在访问中(正在栈帧中)13     // 0 代表该点没有被访问过14     // 1 代表该点及所有有关系的点都被访问过了15     vis[cur] = -1;16     for(int i = 1; i <= n; ++i)17         if(G[cur][i]){18             //若在访问中遇到符合要求且正在调用的点,证明图存在有向环,不存在拓扑排序19             if(vis[i] < 0) return false; 20             else if(!vis[i] && !dfs(i)) return false;21         }22     vis[cur] = 1;23     topo[--t] = cur;24     return true;25 }26 bool toposort(){27     t = n;28     memset(vis, 0, sizeof(vis));29     memset(topo, 0, sizeof(topo));30     for(int i = 1; i <= n; ++i)31         if(!vis[i])32             if(!dfs(i))33                 return false;34     return true;35 }36 int main(){37     while(cin >> n >> m){38         if(n == 0 && m == 0) break;39         memset(G, 0, sizeof(G));40         while(m--){41             int a, b;42             cin >> a >> b;43             G[a][b] = 1;44         }45         if(toposort())46             for(int i = 0; i < n; ++i) cout << topo[i] << " \n"[i == n-1];47     }48     return 0;49 }