PAT (Advanced Level) Practice 1139 First Contact (30分)

雨点打透心脏的1/2处 2023-07-05 10:10 46阅读 0赞

其实代码就不用看了，我写的很菜。主要是看思路，相信大家不会说一点思路没有，大体的代码都编的出来，但是可能漏掉了要点。

下面列举题干的坑：  
（1）题目中并没有说A和B是朋友，B和C是朋友就能推出A和C是朋友。千万不要先入为主，如果你是这种思想的话，你可能就会用并查集去写了，实际上这就是一个简单的图而已。  
（2）0000这个编号是可能存在的。（严格来说0既不是正数，又不是负数，所以他题目就不严谨，但是没办法呀）。我不知道是不是有-0000这样的数据存在，所以我选择用字符串接收数字，看第一位是不是符号来判断正负。

接下来就是思路，思路后面还有需要注意的点：  
（1）我使用邻接列表的形式存储图，然后用gender数组存储每个结点的正负。  
（2）对于每个测试点A B。先找出所有A的同性朋友，再找出B的同性朋友。而后二重循环，判断A的同性朋友是不是B的同性朋友的朋友，若是则符合要求。  
（3）按题目要求排序后输出

**重点**：**若A和B是同性**

（1）则在找A的同性朋友时要排除B，找B的同性朋友时要排除A。否则会出现A-> B-> A ->B这种信息传递路径，这显然是不对的。

（2）传递消息的必须是两个人。也就是说A->C->C->B这种消息传递路径也是错的。

#include <iostream>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    #define boy  1
    #define girl -1
    #define maxn 10000
    using namespace std;
    vector<int> G[maxn];
    int gender[maxn]={0};
    bool visited[maxn]={false};
    int n,m,k;
    struct contact{
        int p1,p2;
        contact(int a,int b){
            p1=a;
            p2=b;
        }
    };
    vector<contact> dfsv;
    bool cmp(contact c1,contact c2){
        if(c1.p1!=c2.p1){
            return c1.p1<c2.p1;
        }
        return c1.p2<c2.p2;
    }
    int change(string s,int &flag){
        if(s[0]=='-'){
            flag=girl;
            s.erase(0,1);
        }else{
            flag=boy;
        }
        int sum=0,p=1;
        for(int i=s.size()-1;i>=0;i--){
            sum+=p*(s[i]-'0');
            p=p*10;
        }
        return sum;
    }
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<m;i++){
            int v1,v2,flag;
            string s1,s2;
            cin>>s1>>s2;
    
            v1=change(s1,flag);
            gender[v1]=flag;
            v2=change(s2,flag);
            gender[v2]=flag;
            G[v1].push_back(v2);
            G[v2].push_back(v1);
        }
        cin>>k;
        for(int i=0;i<k;i++){
            int p1,p2,flag;
            string s1,s2;
            cin>>s1>>s2;
            p1=change(s1,flag);
            p2=change(s2,flag);
    
            vector<int> v1,v2;
            for(int i=0;i<G[p1].size();i++){
                int f=G[p1][i];
                if(gender[p1]==gender[f]&&f!=p2){
                    v1.push_back(f);
                }
            }
            for(int i=0;i<G[p2].size();i++){
                int f=G[p2][i];
                if(gender[p2]==gender[f]&&f!=p1){
                    v2.push_back(f);
                }
            }
    
            vector<contact> result;
            for(int j=0;j<v1.size();j++){
                for(int t=0;t<v2.size();t++){
                    int f1=v1[j],f2=v2[t];
                    bool relate=false;
                    for(int i=0;i<G[f1].size();i++){
                        if(f2==G[f1][i]){
                            relate=true;
                            break;
                        }
                    }
                    if(relate==true&&f1!=f2){
                        result.push_back(contact(f1,f2));
                    }
                }
            }
    
            sort(result.begin(),result.end(),cmp);
            cout<<result.size()<<endl;
            for(int i=0;i<result.size();i++){
                printf("%04d %04d\n",result[i].p1,result[i].p2);
            }
        }
        return 0;
    }