问个问题 为什么我背的并查集union模板这题不行了
  • 板块P2814 家谱
  • 楼主AVLw
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/10/10 11:58
  • 上次更新2023/11/2 14:41:43
查看原帖
问个问题 为什么我背的并查集union模板这题不行了
1021623
AVLw楼主2023/10/10 11:58

看注释 union函数前面的亲戚村村通都好使 这题就不行 得写father[name] = fname

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

map<string, string> father;

string finds(string i) {
    if (i != father[i])
        father[i] = finds(father[i]);
    return father[i];
}

//合并
void unions(string x, string y) {
    father[finds(x)] = finds(y);
}

int main() {
    string name;
    string fname;//父亲名字
    char op;
    while (cin >> op) {
       if (op == '$')
            break;
       cin >> name;
        if (op == '#') {
            fname = name;
            if(!father.count(name))
              father[name] = name;
            
        }
        else if (op == '+') {
          
            father[name] = fname;//为什么unions(name,fname)合并就不行
        }
        else if (op == '?') {
            cout << name << " " << finds(name) << endl;
        }
    }

    return 0;
}

2023/10/10 11:58
加载中...