华为9.27笔试

第一题

给出员工(\(n \leq 100\))和对应的亲属关系，询问能否将其分为两个组合，要求亲属不在同一侧。
要求两个组合中第一个数尽量小。

一眼并查集，即员工i的亲属属于同一个集合，生成一个集合编号j。
记录员工i以及与之互斥的点，用于后续获取员工i互斥的集合编号j。

由于要求组合中第一个数尽量小，将0加入到组合1中，并且记录组合1中已有的集合编号。

遍历并查集记录数组，

1. 每个数互斥的集合不存在组合2中则加入组合2，保证组合2的起始数字最小。
2. 否则查看其互斥集合号是否存在集合1，如果集合1也存在互斥集合号，则输出-1，否则加入集合1

最后输出两个数组

#include<bits/stdc++.h>  
using namespace std;  
int f[105];  
int find(int x) {  
    if (f[x] == x) return x;  
    return f[x] = find(f[x]);  
}  
void merge(int a, int b) {  
    int sa = find(a);  
    int sb = find(b);  
    if (sa == sb) return;  
    f[sa] = sb;  
}  
int main() {  
    int n;  
    cin >> n;  
    for (int i = 0; i < n; i++) {  
        f[i] = i;  
    }  
    unordered_map<int,int>mp;  
  
    for (int i = 0; i < n; i++) {  
        int tmp;  
        int pre;  
        cin >> pre;  
        while (cin >> tmp) {  
            merge(pre, tmp);  
            if (getchar() == '\n') break;  
        }  
        mp[i] = tmp;  
    }  
    for (int i = 0; i < n; i++) {  
        find(i);  
    }  
  
    vector<int> nums1;  
    vector<int> nums2;  
    unordered_map<int,int>mp1;  
    unordered_map<int,int>mp2;  
    nums1.push_back(0);  
    mp1[f[0]] = 1;  
    for (int i = 1; i <n; i++) {  
        if (mp2.count(f[mp[i]])) {  
            if (!mp1.count(f[mp[i]])) {  
                nums1.push_back(i);  
                mp1[f[i]] = 1;  
            }  
            else {  
                cout << -1 << endl;  
                return 0;  
            }  
        }  
        else {  
            nums2.push_back(i);  
            mp2[f[i]] = 1;  
        }  
    }  
    int n1 = nums1.size();  
    int n2 = nums2.size();  
    for (int i = 0; i <n1; i++) {  
        if (i == n1 - 1) cout << nums1[i] << endl;  
        else cout << nums1[i] << " ";  
    }  
    for (int i = 0; i < n2; i++) {  
        if (i == n1 - 1) cout << nums2[i] << endl;  
        else cout << nums2[i] << " ";  
    }  
  
    return 0;  
}

第二题

给定起始点s，中间点inter和终点e,请问从s出发坐公交经过inter到达终点e乘坐的公交总数为多少？
接下来给出line条公交线路对应的站点。

考虑从中间点inter出发到达两侧，枚举出发的公交路线，得到对应的乘坐总数。
枚举往两侧出发的公交路线号，维持对应的最优公交路线。

bug: 左右侧相同的公交路线可能不仅存在于inter位置，sc函数应该返回最优的路径，最后求出两侧不同的公交路线数目。当前代码求取的是转车次数。(反正能过样例)

ps: 并查集检测能到达输出3，不能到达输出-1也能骗60%呢

#include<bits/stdc++.h>  
using namespace std;  
int main() {  
    int starte,intere,ende,lines;  
    cin >> starte >> intere >> ende;  
    cin >> lines;  
  
    unordered_map<int, vector<int>>mp;  
    for (int i = 0; i < lines; i++) {  
        int num;  
        cin >> num;  
        for (int j = 0; j < num; j++) {  
            int tmp;  
            cin >> tmp;  
            if (mp.count(tmp)) mp[tmp].push_back(i);  
            else mp[tmp] = vector<int>{i};  
        }  
    }  
    unordered_map<int, int>edges[505];  
    for (auto[k,v]:mp) {  
        int m = v.size();  
        for (int i = 0; i < m; i++) {  
            for (int j = i + 1; j < m; j++) {  
                if (!edges[v[i]].count(v[j])) edges[v[i]][v[j]] = 1;  
                if (!edges[v[j]].count(v[i])) edges[v[j]][v[i]] = 1;  
            }  
        }  
    }  
    function<int(int,int, int)> sc = [&](int start, int sl, int end) {  
        unordered_map<int,int> result;  
        int ocup[505];  
        memset(ocup,0,sizeof(ocup));  
        for (int i:mp[end]) result[i] = 1;  
        int res = 1;  
        queue<int>q;  
        if (result.count(sl)) return res;  
        else {  
            ocup[sl] = 1;  
            q.push(sl);  
        }  
        while (!q.empty()) {  
            res++;  
            int s = q.size();  
            for (int i = 0; i < s; i++) {  
                int t = q.front();  
                q.pop();  
                for (auto[to,_]:edges[t]) {  
                    if (ocup[to] == 0) {  
                        if (result.count(to)) {  
                            return res;  
                        }  
                        q.push(to);  
                        ocup[to] = 1;  
                    }  
                }  
            }  
        }  
        return -1;  
    };  
    unordered_map<int, int>resset1;  
    unordered_map<int, int>resset2;  
    for (int i:mp[intere]) {  
        resset1[i] = sc(intere,i, starte);  
        resset2[i] = sc(intere,i, ende);  
    }  
    int res = 505;  
    for (auto [k1,v1]:resset1) {  
        for (auto [k2,v2]:resset2) {  
            if (v1 == -1 || v2 == -1) continue;  
            if (k1 == k2) res = min(res, v1 + v2 - 1);  
            res = min(res, v1 + v2);  
        }  
    }  
    if (res == 505) cout << -1 << endl;  
    else cout << res << endl;  
    return 0;  
}