#1174 : 拓撲排序·一

時間限制:10000ms 單點時限:1000ms 內存限制:256MB

描述

由于今天上課的老師講的特別無聊，小Hi和小Ho偷偷地聊了起來。

小Ho：小Hi，你這學期有選什么課么？

小Hi：挺多的，比如XXX1,XXX2還有XXX3。本來想選YYY2的，但是好像沒有先選過YYY1，不能選YYY2。

小Ho：先修課程真是個麻煩的東西呢。

小Hi：沒錯呢。好多課程都有先修課程，每次選課之前都得先查查有沒有先修。教務公布的先修課程記錄都是好多年前的，不但有重復的信息，好像很多都不正確了。

小Ho：課程太多了，教務也沒法整理吧。他們也沒法一個一個確認有沒有寫錯。

小Hi：這不正是輪到小Ho你出馬的時候了么！

小Ho：哎？？

我們都知道大學的課程是可以自己選擇的，每一個學期可以自由選擇打算學習的課程。唯一限制我們選課是一些課程之間的順序關系：有的難度很大的課程可能會有一些前置課程的要求。比如課程A是課程B的前置課程，則要求先學習完A課程，才可以選擇B課程。大學的教務收集了所有課程的順序關系，但由于系統故障，可能有一些信息出現了錯誤。現在小Ho把信息都告訴你，請你幫小Ho判斷一下這些信息是否有誤。錯誤的信息主要是指出現了"課程A是課程B的前置課程，同時課程B也是課程A的前置課程"這樣的情況。當然"課程A是課程B的前置課程，課程B是課程C的前置課程，課程C是課程A的前置課程"這類也是錯誤的。

提示：拓撲排序

輸入

第1行：1個整數T，表示數據的組數T(1 <= T <= 5)
接下來T組數據按照以下格式：
第1行：2個整數，N,M。N表示課程總數量，課程編號為1..N。M表示順序關系的數量。1 <= N <= 100,000. 1 <= M <= 500,000
第2..M+1行：每行2個整數，A,B。表示課程A是課程B的前置課程。

輸出

第1..T行：每行1個字符串，若該組信息無誤，輸出"Correct"，若該組信息有誤，輸出"Wrong"。

樣例輸入

2 2 2 1 2 2 1 3 2 1 2 1 3

樣例輸出

Wrong Correct

/*/ 拓撲排序的第一題，為了理解拓撲排序一開始用鄰接矩陣寫了一個，發現跟題目說的一樣會爆內存，后面發現，STL的隊列更加簡單易懂，果斷寫了一個A題。AC代碼： /*/

?

#include"algorithm" #include"iostream" #include"cstring" #include"string" #include"cstdio" #include"vector" #include"cmath" #include"queue" using namespace std; #define memset(x,y) memset(x,y,sizeof(x)) #define MX 100000 + 10/***********************************************************超時，超內存-寫法-鄰接矩陣 *********************************************************** int cnt; int map[MX][MX]; //鄰接矩陣 int indegree[MX]; //入度void toposort(int map[MX][MX],int indegree[MX],int n,int m){for(int i=1;i<=m;i++){//進行m次歷遍for(int j=1;j<=n;j++){ //j 枚舉每一個點if(!indegree[j]){ //如果這個點入度為0，標記已經查過了。indegree[j]--;for(int k=1;k<=n;k++){ //檢查這個點的其他邊，并且消掉這些邊。if(map[j][k]==1){indegree[k]--; //入度--cnt--; //清除該條有向邊}}}}} }int main() {int T;int n,m,st,ed;scanf("%d",&T);while(T--) {scanf("%d%d",&n,&m);cnt=0;memset(map,0);memset(indegree,0);for(int i=0; i<m; i++) {scanf("%d%d",&st,&ed);map[st][ed]=1; //該有向邊存在indegree[ed]++; //入度++cnt++;//有向邊的數量}toposort(map,indegree,n,m);cout<<cnt<<endl;if(cnt==0) puts("Correct"); //如果有向邊數變為0 則說明是正確的else puts("Wrong");}return 0; } //*********************************************************//***********************************************************queue ***********************************************************/int T,n,m,head[MX],cnt,p[MX]; queue<int>q;struct node {int e,next; } edge[MX];void add(int st,int ed) {edge[cnt].e=ed;edge[cnt].next=head[st];head[st]=cnt++; }int main() {int i,st,ed,ans;scanf("%d",&T);while(T--) {ans=0;cnt=1;scanf("%d%d",&n,&m);memset(p,0);memset(head,-1);for(i=0; i<m; i++) {scanf("%d%d",&st,&ed);add(st,ed);p[ed]++;}for(i=1; i<=n; i++) //把入度為0的壓入隊列 if(!p[i]) {q.push(i);ans++;}while(!q.empty()) {int k=q.front();q.pop();for(i=head[k]; i!=-1; i=edge[i].next) {int v=edge[i].e;p[v]--;if(!p[v]) { //把入度為0的壓入隊列 q.push(v);ans++; //標記入度為0的數量 }}}if(ans==n)puts("Correct"); //如果入度為0的節點等于總點數 則說明是正確的else puts("Wrong");}return 0; } //*********************************************************/

　　

轉載于:https://www.cnblogs.com/HDMaxfun/p/5736292.html

總結

以上是生活随笔為你收集整理的ACM: hihicoder #1174 : 拓扑排序·一 STL- queue的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。