求此题解（还是测试数据有问题- -） - C语言论坛

已结贴√ 问题点数：88 回复次数：11

求此题解（还是测试数据有问题- -）

时间限制 : 1000 ms 内存限制 : 32 MB
题目描述

有一天boss给小明发了一套游戏规则，声称这是小明接下来任务。十来页的规则文档看得头有点晕，
并且小明对规则的可行性表示了怀疑，因为文档充斥了X条件的产生要依赖于Y产生。如果X依赖于或
者间接依赖于Y，而且Y依赖或者间接依赖于X那么规则就出问题了或者是X可能依赖于错误的条件Y 那也是规则错误。
对此，小明想验证一下规则的可行性（不理解可以看见解释再不理解就无视这个题好了^-^）。
输入描述

最多有100 case
每个样例开始有1个N表示下面有N个不同的条件（0<N<=100），每行第一个数字X(0<=X<N)代表某一个条件，接着是
一个数字K，表示后面有K个X需要依然的条件。
输出描述

如果规则在逻辑上没有问题，则输出YES,否则错误集合的内的最小数字。

样例输入

2
0 0
1 1 0
2
0 1 1
1 1 0
8
0 1 6
1 0
2 1 4
3 2 2 1
4 1 3
5 0
6 1 0
7 2 5 6
4
0 1 3
1 1 3
2 1 1
3 1 2
4
0 0
1 1 3
2 1 1
3 2 0 2
样例输出

YES
0
0
2
0
1

解释：第三个样例0和6为相互依靠故为一个错误集合 2 3 4相互依靠也为一个错误集合注意这里的1不依靠任何条件故不属于错误输出就是0 2 第四个样例中注意由于0的条件是3，而3在错误集合里那么0也是错误的也就是说原因是错误的结论也就是错误的但是如果结果是错误的，原因是不一定错误的如第五组样例 1 2 3这个错误集合不影响到0这个条件因为0这个条件的发生是没有前提的。

搜索更多相关主题的帖子: 可行性　游戏　时间　明发　

第 2 楼

得分:0

我写的代码，顺便加了点注释，大家帮忙看看是我的理解有问题呢？？还是我的代码有问题呢？？还是测试数据有问题呢？？
这题目的OJ地址为： http://info.zjfc.

#include<iostream>
#include<queue>
using namespace std;

int map[109][109],count1[109],flag[109],n,min2,flag1;
#define MAX 109
void topological_sort(){
    queue<int> line;
    for(int i=0; i<MAX; ++i){
        if( count1[i]==0 ) line.push(i);
    }
    while(!line.empty()){
        int t=line.front();
        line.pop();
        for(int i=0; i<MAX; ++i){
            if(map[t][i]){
                map[t][i]=0;
                count1[i]--;
                if(count1[i]==0) line.push(i);
            }
        }
    }
}
void DFS( int x){
    for(int i=0; i<MAX; ++i){
        if( !flag[i] && (map[x][i] || map[i][x]) ){
            flag[i]=1;
            ++flag1;
            if(i<min2) min2=i;
            DFS(i);
        }
    }
}
int main(){
    while( cin >> n ){
        memset(map,0,sizeof(map));
        memset(count1,0,sizeof(count1));
        queue<int> line2;
        for(int i=0; i<n; ++i ){
            int m,k;
            cin >> m >> k;
            if(k==0) continue;
            for(int j=0; j<k; ++j){
                int a;
                cin >> a;
                map[a][m]=1;
                count1[m]++;
            }
        }
        topological_sort();//先进行拓扑排序，把依赖关系正确的点去掉
        memset(flag,0,sizeof(flag));
        for(int i=0; i<MAX; ++i){ //穷举每个点，看是否为错误集合
            if(!flag[i]){
                flag[i]=1;
                flag1=0; //标记是否是一个错误集合（拓扑排序后如果集合中的元素个数大于2，那就说明一定是错误集合）
                min2=i;
                DFS(i);
               if(flag1) line2.push(min2);
            }
        }
        if(!line2.empty()){
            while(!line2.empty()){
                int t=line2.front();
                line2.pop();
                cout << t << endl;
            }
        }
        else cout << "YES" << endl;
    }
    return 0;
}