PAT1146 Topological Order-白红宇

PAT1146 Topological Order

阅读量：7010 次

发布时间：2019-06-27

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

原题链接：

解析：这题我第一次做只过了4个点，最后一个超时了。第一次方法是先用删边法求出所有拓扑排序，然后用map< vector<int>,bool>来检查给出的拓扑排序是否正确。然后我想用dfs计算拓扑排序的方法改进，但是书上显然没有对这种方法详细教程，因此试了四五次都过不了。

其实这题可以用删边法的思想，先读入每个点，计算好他的入度，以及他的下一个节点。将所给的拓扑排序挨个判断入度是否为0，若是，则将其所有子节点入度-1，否则返回false。

代码实例：

#include
    
     #include
     
      #include
       #include
       
        using namespace std;typedef vector
        
          vec;vec ans;int n,m;bool judge(vector
         
           &nex,int u,int pre[]){ if(pre[u]) return false; for(int i = 0;i < nex[u].size();i++){ pre[nex[u][i]]--; } return true;}bool solve(vector
          
            &nex,int tmp[],int pre[]){ for(int i = 0;i < n;i++) if(judge(nex,tmp[i],pre) == false) return false; return true;}int main(){ int pre[1005]; cin >> n >> m; vector
           
             nex(n+5); int a,b; for(int i = 0;i < m;i++){ cin >> a >> b; pre[b]++; nex[a].push_back(b); } int k; cin >> k; ans.clear(); for(int i = 0;i < k;i++){ int tmp[n]; for(int j = 0;j < n;j++) cin >> tmp[j]; int pre2[1005]; for(int j = 0;j <= n;j++) pre2[j] = pre[j]; if(solve(nex,tmp,pre2) == false) ans.push_back(i); } for(int i = 0;i < ans.size();i++){ if(i == 0) cout << ans[i]; else cout << " " << ans[i]; } return 0;}

转载于:https://www.cnblogs.com/long98/p/10352204.html

你可能感兴趣的文章