面试遇到好老中，只出了一道union find 算放水嘛
面试是否放水取决于题目难度与考察目的，Union Find 存在争议。
1. 关键信息
- UF 模板默写常见，路径压缩与按秩合并需熟练（#4 #9 #14）。
- 题目为无向图判环，输出首个成环边（#29 #25）。
- 替代解法：DFS 或拓扑剥圈（#21 #27）。
- 难度分歧：部分认为太简单（#3 #13 #18），部分认为需刷题（#14）。
2. 羊毛/优惠信息
无
3. 最新动态
无
4. 争议或不同意见
- 是否放水两极分化：文化 fit 与模板熟练度 vs 基础 CS 知识（#2 #12 #18）。
- 题目是否唯一解：UF 与 DFS/拓扑排序可行性对比（#13 #21 #27）。
- 面试策略：结果导向 vs 过程考察（#10 #19）。
5. 行动建议
- 熟练 UF 模板与变种，准备多解法应对面试。
怎么感觉也不是tag
要不是上次面大香蕉被人说不会并茶几，估计这次也写不上。
没有放不放水，culture fit，personality也是考察的一部分…
这不算放水啊，我觉得面难了
我一下子竟然想不起来 union find 该怎么做
开局直接开始默写
class DSU {
vector<int> p, r;
public:
DSU(int n): p(n), r(n,0){ iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
void unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
}
};
【引用自 打豆豆】:
水，culture fit
master豆你看我fit吗
你们招人要最优解才能fit么 呜呜
鸡肉记忆是吧
对
模版什么的都刻在dna里面（不是
UF算个屁放水 2 Sum才算
那他还是坏老中
肯定不是啊 看想不想对方成为自己未来的同事…
我以前问的题有很多种方法可以做，其中一种是用冰茶几，随便你用哪种方法做出来我就给过。你确定这题只能用冰茶几做吗？只能就是没放水。
UF 绝对算放水。因为它虽然有模板，但如果你没练过，现场想出 find 的路径压缩和 union 的按 rank 合并，难度其实不小。老中面试官出这题，本质上是想看你 “有没有正经刷过题”。只要你模板写得溜，他就觉得你是“同类”，大家以后在组里能一起卷。
graph里找环 输出最后一个成环的edge
典型uf 不用并查集就dfs慢慢找了吧 我估计
恭喜拿到大包成为人上人
还有一轮
这不叫放水 你也不能assume所有面试都是组面
只要有基本CS知识 没刷过题的也能现场想出来的题才叫放水 比如2 Sum
能过就是本事，别管放不放水了，结果导向
老哥现在强得可怕
像刚高考完的状态
直接topological sort，一层层的把自由的vertex抛开就行了。最后剩下的一坨就是loop
dna里除了dna什么都有
无向图呢
【引用自 nin11】:
输出最后一个成环的edge
有可能边有添加的顺序，那确实UF最自然
对的 只有添加顺序
看来还是坏老中
我被烙印问过UF。这种能套模版（而且模版很短也不难现场推导）的我统一视作送分
一样的，直接计算每个vertex上有几个edge，然后 每次都从 edge数量为1的vertex 出发，他们相邻的vertex 每次edge数减一， 如果剪完恰好为1就push到q里面. 这样剥完，剩下的core就是loop在的地方。
ah。。 我好像明白你的意思了。。。 你那个题是那个 vertex = edge - #roots 啥的那个题把。。。
好像不是 （但是我开始上课了
这题应该是无向图n个节点，给一个列表，列表元素是(u, v)指连接一条u, v无向边，问添加哪个元素以后出现第一个无向环
可能换个泥潭卷王就还要支持删边才行，就得维护森林了
放水怎么着也得是 threesom two sum吧
以后手工编程可不多了，且编且珍惜
i see. 那直接看有多少个tree root就行了
【引用自 nin11】:
看来还是坏老中
你都不怕 这个坏老中
万一也上坛 可咋整
声音小一点 嘘嘘嘘
这绝对算
你说的2sum 根本不可能在公司的题库里 就算他想出 他也出不了
相比之下这题绝对算简单了
我觉得我跟豆豆老师南辕北辙，毕竟我只想减肥，而豆老师只想干饭
如果是模版uf那还是算放水了
如果是我想放水可能出个更简单的number of islands
好奇。并茶几是什么？是道题还是？