Home PAT 1139 First Contact
Post
Cancel

PAT 1139 First Contact

Link

注意, 第一次输入 id 时要用字符串, 因为 -0000 也是女生啊! 存储好了之后查询的时候就可以用数字读了. 这个地方会卡测试点 2、3. 再就是输出的时候要是 4 位数字, 这也会卡一个测试点. 另外最最重要的是, 存储 same-gender friends 的时候不要重复存储, 因此用 set 不仅能保证唯一性还可以自动排序. 在 Find 函数的两层 for 循环查找的时候, C 不能找 A, B 不能找 A 和 C. 因为一定要是两个中间人.

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
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
const int N=10001;
int n,m,k,a,b;
vector<set<int>>same(N);
bool friends[N][N];
void Find(){
    vector<pair<int,int>>ans;
    for(auto i=same[a].begin();i!=same[a].end();++i){
        int x=*i;
        if(x==b) continue;
        for(auto j=same[b].begin();j!=same[b].end();++j){
            int y=*j;
            if(y!=a&&y!=x&&friends[x][y])
                ans.push_back({x,y});
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)
        printf("%04d %04d\n",ans[i].first,ans[i].second);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        string s1,s2;
        cin>>s1>>s2;
        if(s1==s2) continue;
        a=stoi(s1),b=stoi(s2);
        if((s1[0]=='-'&&s2[0]=='-')||(s1[0]!='-'&&s2[0]!='-')){
            a=a<0?-a:a,b=b<0?-b:b;
            same[a].insert(b),same[b].insert(a);
        }
        a=a<0?-a:a,b=b<0?-b:b;
        friends[a][b]=friends[b][a]=true;
    }
    scanf("%d",&k);
    while(k--){
        scanf("%d%d",&a,&b);
        a=a<0?-a:a,b=b<0?-b:b;
        Find();
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.