编译错误（C++）

coding>C++
1.4k 词

题目描述

在程序员编写程序的时候，通常会引用其他文件，而引用的文件也会引用其它的头文件。但是出现循环引用的现象编译时便会报错。例如A引用了B，B引用了C，C引用了A，那么就产生了循环引用（Circular reference）。考虑另外一个情况，A引用了B和C，B引用D，C引用D，虽然D被引用了两次，但是没有出现循环引用。 

输入

第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有多少个引用关系。接下来n行每行有2个字符串a,b，用空格分隔，代表a引用了b。其中$T<=50$, $n<=10^5$，每个字符串的长度不超过100。

输出

共T行。若不会产生编译错误则输出Passed，否则输出Failed。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
8
client.cpp client.h
client.h server.h
server.cpp server.h
server.h common.h
client.h common.h
common.cpp common.h
common.h gtest.h
common.h glog.h
4
work.cpp client.cpp
client.cpp server.cpp
server.cpp adhoc.cpp
adhoc.cpp work.cpp

样例输出

1
2
Passed
Failed

提示

拓扑排序/有向无环图 不可n^2算法

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
  
int main(){
    int t,n;
    int num1=0,num2=0;
    char a[110],b[110];
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        map<string, int> hasha;
        map<string, int> hashb;
        map<string,int>::iterator ita,itb;
        scanf("%d",&n);
        for(int j=0;j<n;j++)
        {
            scanf("%s%s",a,b);
            hasha[a]++;
            hashb[b]++;
        }
        int flag=0;
        for(ita=hasha.begin();ita!=hasha.end();ita++)
        {
            for(itb=hashb.begin();itb!=hashb.end();itb++)
            {
                string s1=ita->first;
                string s2=itb->first;
                if(s1==s2&&hasha[s1]!=hashb[s2]) 
                {
                    flag=1;
                    break;
                }
            }
        }
        if(flag) printf("Passed\n");
        else printf("Failed\n");
    }
    return 0;
}