经典问题-Ordering Tasks

dfs函数的返回值表示是否成环，若存在有向环，则不存在拓扑排序。不包含有向环的有向图称为有向无环图（DAG）

可以借助DFS完成拓扑排序，在访问完一个结点时把他加入当前拓扑序的首部。

举个栗子：比如一个（1,2），（1,3），（2，3)的有向无环图，就先搜索1,再递归搜索2，再搜索3，3没有出度了，于是放进拓扑序尾=，再回到2,2除3外没有出度，再放入拓扑序，再回到1,1除2,3没有出度，放入拓扑序

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <set>

 #include <vector>

 #include <cctype>

 #include <iomanip>

 #include <sstream>

 #include <climits>

 #include <queue>

 #include <stack>

 using namespace std;

 typedef long long ll;

 #define INF 0X3f3f3f3f

 const ll MAXN = 1e3 + ;

 const ll MOD = 1e9 + ;

 int mp[MAXN][MAXN];

 int vis[MAXN];

 int topo[MAXN], t;//topo数组存放最后拓扑排序结果

 int n,k,m;

 bool dfs(int u)//判环

 {

     vis[u] = -; //访问标志

     for(int i=;i<=n;i++)

     {

         if(mp[u][i])

         {

             if(vis[i]==-) return false;//存在有向环，退出

             if(!vis[i]&&!dfs(i)) return false;

         }

     }

     topo[--k]=u;

     vis[u]=;

     return true;

 }

 bool toposort()

 {

     memset(vis,,sizeof(vis));

     k=n;

     for(int i=;i<=n;i++)

          if(!vis[i]&&!dfs(i)) return false;

     return true;

 }

 void print()

 {

     for(int i=;i<n;i++)

     {

         if(i) cout<<' ';

         cout<<topo[i];

     }

     cout<<endl;

     return ;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     while (cin >> n >> m&&(n|m))

     {

         memset(mp,,sizeof(mp));

         for (int i = ; i < m; i++)

         {

             int a,b;

             cin>>a>>b;

             mp[a][b]=;

         }

         if(toposort())

         print();

         else

         cout<<"sorry to say there is no DAG"<<endl;//跟题目并没有关系...

     }

     return ;

 }

加个队列写法..

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <set>

 #include <vector>

 #include <cctype>

 #include <iomanip>

 #include <sstream>

 #include <climits>

 #include <queue>

 #include <stack>

 using namespace std;

 typedef long long ll;

 #define INF 0X3f3f3f3f

 const ll MAXN = 1e3 + ;

 const ll MOD = 1e9 + ;

 int n, m;

 int degree[MAXN][MAXN];

 int indegree[MAXN];

 int topo[MAXN];

 void toposort()

 {

     int cnt = ;

     queue<int> que;

     for (int i = ; i <= n; i++)

         if (!indegree[i])

             que.push(i);

     int cur;

     while (!que.empty())

     {

         cur = que.front();

         que.pop();

         topo[cnt++] = cur;

         for (int i = ; i <= n; i++)

         {

             if (degree[cur][i])

             {

                 indegree[i]--;

                 if (!indegree[i])

                     que.push(i);

             }

         }

     }

     return;

 }

 void print()

 {

     for (int i = ; i < n; i++)

     {

         if (i)

             cout << ' ';

         cout << topo[i];

     }

     cout << endl;

     return;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     while (cin >> n >> m && (n | m))

     {

         memset(degree, , sizeof(degree));

         memset(indegree, , sizeof(indegree));

         while (m--)

         {

             int a, b;

             cin >> a >> b;

             if (!degree[a][b])

             {

                 degree[a][b] = ;

                 indegree[b]++;

             }//处理重边

         }

         toposort();

         print();

     }

     return ;

 }

巴特西

拓扑排序（基于dfs+基于队列）

经典问题-Ordering Tasks

最新文章

热门文章