POJ2367 拓扑排序 裸题 板子题

http://poj.org/problem?id=2367

队列版

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <map>

 #include <vector>

 using namespace std;

 const int maxn = 1e3+;

 const int maxm = 1e4+;

 const int inf = 0x3f3f3f3f;

 const int mod = ;

 const double epx = 1e-;

 typedef long long ll;

 const ll INF = 1e18;

 const double pi = acos(-1.0);

 vector<int> g[maxn];

 int rudu[maxn],order[maxn],vis[maxn];

 int n,m,cnt;

 void toposort()

 {

     priority_queue<int,vector<int>,greater<int> > q;

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

         if(rudu[i]==)

             q.push(i),vis[i]=;

     while(!q.empty())

     {

         int v=q.top();q.pop();

         order[cnt++]=v;

         for(int i=;i<g[v].size();i++)

         {

             int u=g[v][i];

             rudu[u]--;

             if(rudu[u]==)

                 q.push(u),vis[u]=;

         }

     }

 }

 int main()

 {

     cin>>n;

     memset(rudu,,sizeof(rudu));

     memset(order,,sizeof(order));

     memset(vis,,sizeof(vis));

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

     {

         int u,v;

         do{

             cin>>v;

             if(v!=)

                 g[i].push_back(v),rudu[v]++;

         }while(v!=);

     }

     cnt=;toposort();

     if(cnt==n)

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

         {

             if(i==n-)

                 cout<<order[i]<<endl;

             else

                 cout<<order[i]<<" ";

         }

     //else

         //cout<<"no"<<endl;

 }

dfs版

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <map>

 #include <vector>

 using namespace std;

 const int maxn = 1e3+;

 const int maxm = 1e4+;

 const int inf = 0x3f3f3f3f;

 const int mod = ;

 const double epx = 1e-;

 typedef long long ll;

 const ll INF = 1e18;

 const double pi = acos(-1.0);

 int g[maxn][maxn];

 int c[maxn],n,m;

 int topo[maxn],t;

 bool dfs(int u)    //思想是 一直搜找到当前没有出度的点 存到数组里 逆序操作

 {

     c[u]=-;       //c数组 0表示没有访问过 -1表示还在栈中尚未返回 1表示已经访问完

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

     {

         if(g[u][v])

         {

             if(c[v]<)

                 return false;  //当前节点已经在栈中了 说明有环 返回false

             else if(!c[v]&&!dfs(v))

                 return false;  //若子节点搜索过程中遇到环 向前返回失败

         }

     }

     c[u]=;topo[t--]=u;       //遍历完之后存到数组里

     return true;

 }

 bool toposort()

 {

     t=n;

     memset(c,,sizeof(c));

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

         if(!c[u]&&!dfs(u))

             return false; //如果当前节点没有被访问过 进行dfs 若返回false 说明环 不能拓扑排序

     return true;

 }

 int main()

 {

     cin>>n;

     memset(g,,sizeof(g));

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

     {

         int u;

         while()

         {

             cin>>u;

             if(u==)

                 break;

             g[i][u]=;

         }

     }

     if(toposort())

     {

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

                 cout<<topo[i]<<" ";

             cout<<topo[n]<<endl;

     }

 }