讨论/求职面试/字节面试题目求解/

小明是图书管理员,要把若干图书放到书架上。但是书的存放有要求,老明会告诉小明这些要求,1代表两本图书要放在一起,2代表两本图书不能放一起

例如:
1 1 3表示要求图书1和3要放一起
1 1 4要求图书1和4要放一起
2 1 4要求图书2和4不能放在一起

可是老明有些老糊涂了,有些要求达不到例如
1 1 3要求图书1和3要放一起
1 1 2要求图书1和2要放一起
2 2 3要求图书2和3不能放在一起(达不到)

现先输入n(n个命令)
然后下面n行每行输入3个数字,
要求在1命令都满足的情况下,有多少个2要求无法达到?

6
共 6 个回复

建一个并查集,把所有1操作要求放一起的书union起来,然后遍历2操作中的书,如果连同则count++

3

跑了一下测试样例,是可以的
注意这里图书的编号是不确定范围的,因此要用哈希表,不能用数组

#include <bits/stdc++.h>
using namespace std;

class UF {
public:
    unordered_map<int, int> parent;

    UF() {}

    void merge(int x, int y) {
        if(find(x) == -1) parent[x] = x;
        if(find(y)== -1) parent[y] = y;
        x = find(x);
        y = find(y);
        if(x == y) return;
        parent[x] = y;
    }

    int find(int x) {
        if(parent.count(x) == 0)
            return -1;
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    bool isConnected(int x, int y) {
        return find(x) != -1 && find(y) != -1 && find(x) == find(y);
    }
};


int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    UF uf;

    vector<pair<int, int>> query;
    while(n--) {
        int a,b,c;
        cin >> a >> b >> c;
        if(a == 1)
            uf.merge(b,c);
        else if(a == 2)
            query.push_back({b,c});
    }
    
    int res = 0;
    for(auto &[x,y] : query) {
        res += uf.isConnected(x,y);
    }
    cout << res << endl;
    return 0;
}

一眼并查集。

并查集,而且入门级的并查集

并查集

写错了!应该是2 2 4代表2和4不能在一起