ZCMU—1606

1606: 大二上之锋芒显露

Time Limit: 1 Sec  Memory Limit: 128 MB [Submit][Status][Web Board]

Description

这个时候的你在学习数据结构与算法，这个时候你可以轻松的判断老师的排的课表对不对了，因为每一门课都有先修课。所以。。。

Input

第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的前置课程。

Output

第1..T行：每行1个字符串，若该组信息无误，输出"Correct"，若该组信息有误，输出"Wrong"。

Sample Input

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

Sample Output

Wrong Correct

【分析】

不错的一道题...记录每门课的先修课有几门，然后在每门课记录它是哪几门课的先修课.. 类似拓扑排序，入度为0的课开始删除，直到入度为0的课删光，然后判断删除的课够不够n门，或者判断剩余还有没有课没有被删除。就可以判断信息是否有误. 用比较容易懂的话说就是 把当前已经没有先修课的一门课从容器中删除,也就是删除a.end()，在删除这门课的时候同时把他儿子节点的入度减一。如果某一门课的入度为0，那么把他加入容器a. 直到a容器为空。判断课程信息即可。 很不错的一道题。。。但是奈何....杰哥的数据真心硬。。居然有不存在这门课的情况需要考虑.... 直接导致了我1/16的提交... 比如n=2 但是我输入的A和B可能会出现4,5......我去 【代码】 #include <bits/stdc++.h> using namespace std; int n,m; vector <int >a[1010000]; int f[1010000]; vector<int>q; void judge() {     q.clear(); for(int i=1;i<=n;i++)         if(f[i]==0)          { q.push_back(i);     //printf("%d*****\n",i); } int sum=0;     while(!q.empty())     {         int x=q.back();         q.pop_back();         sum++;         for(int i=0;i<a[x].size();i++)         {         // cout<<a[x][i]<<' '<<f[a[x][i]]<<endl;         f[a[x][i]]--; //  cout<<a[x][i]<<' '<<f[a[x][i]]<<endl;             if(f[a[x][i]]==0) q.push_back(a[x][i]);         }     }     if(sum<n)  printf("Wrong\n");     else printf("Correct\n"); } int main() {     int pp;scanf("%d",&pp);     while(pp--)     {     int t=0;         scanf("%d%d",&n,&m);         memset(f,0,sizeof(f));         for (int i=1;i<=n;i++) a[i].clear();         for (int i=0;i<m;i++)         {             int x,y;scanf("%d%d",&x,&y);             a[x].push_back(y);             f[y]++;             if (x<=0 || x>n || y<=0 || y>n) t=1;         }         if (n==1) printf("Correct\n");         else         if (t) printf("Wrong\n");         else         judge();     }     return 0; }