※ 引述《huangwh (香肠)》之铭言： : 你是说 3的妈妈为2 : 2的妈妈为1 : 最後 1 的妈妈就是6 : 也就是(6,1) : 是这样子吗? : 方便用我原本的例子 : 来讲解一下可以吗? : 谢谢 : 但是我就是不知道要怎将这断语法用c++写出来~!! 不考虑效率什麽的问题的话 最简单的方法就是: 假设你有七个点好了 那就 maintain 7 个 circular link list 初始值就是大家指着自己 ０┐ １┐ ２┐ ３┐ ４┐ ５┐ ６┐ ↑│ ↑│ ↑│ ↑│ ↑│ ↑│ ↑│ └┘ └┘ └┘ └┘ └┘ └┘ └┘ next operation 有分两类, 一个是把 (x, y) 归成同一类 这里称之为 Union(x,y) 一个是查 (x, y) 是否为同一类 这里称之为 isSameGroup(x,y) 每次先查查他们在不在同一个 group (用 isSameGroup(x,y)) 如果已经在同一个 group 了, 就 ignore, 就是你 * 的那类 否则就用 Union(x,y) 把他们组合起来 (5,0) 把 5 拿出来, 它现在是: 顺着它的 next link 往下走 ５┐ 直到走回自己都没有看到 0 ↑│ 所以 isSameGroup(5,0) 就是 false └┘ 我们就要进行 Union(5,0) 的动作 ┌─┐ │ ↓ ０ ５ １┐ ２┐ ３┐ ４┐ ６┐ ↑ │ ↑│ ↑│ ↑│ ↑│ ↑│ └─┘ └┘ └┘ └┘ └┘ └┘ (3,2) 把 3 拿出来, 它现在是: 顺着它的 next link 往下走 ３┐ 直到走回自己都没有看到 2 ↑│ 所以 isSameGroup(3,2) 就是 false └┘ 我们就要进行 Union(3,2) 的动作 ┌─┐ ┌─┐ │ ↓ │ ↓ ０ ５ ２ ３ １┐ ４┐ ６┐ ↑ │ ↑ │ ↑│ ↑│ ↑│ └─┘ └─┘ └┘ └┘ └┘ (6,1) 把 6 拿出来, 它现在是: 顺着它的 next link 往下走 ６┐ 直到走回自己都没有看到 1 ↑│ 所以 isSameGroup(6,1) 就是 false └┘ 我们就要进行 Union(6,1) 的动作 ┌─┐ ┌─┐ ┌─┐ │ ↓ │ ↓ │ ↓ ０ ５ ２ ３ １ ６ ４┐ ↑ │ ↑ │ ↑ │ ↑│ └─┘ └─┘ └─┘ └┘ (2,1) 把 2 拿出来, 它现在是: 　┌─┐ │ ↓ 顺着它的 next link 往下走 ２　３ 直到走回自己都没有看到 1 ↑　│ 所以 isSameGroup(2,1) 就是 false └─┘ 我们就要进行 Union(2,1) 的动作 ┌─┐ ┌─┐ ┌─┐ │ ↓　│ ↓ │ ↓ ２ ３→１ ６ ０ ５ ４┐ ↑ │ ↑ │ ↑│ └─────┘ └─┘ └┘ (6,3)* 把 6 拿出来, 它现在是: 　┌─┐ ┌─┐ │ ↓　│ ↓ 顺着它的 next link 往下走 ２　３→１ ６ 直到走回自己前遇到了 3 !! ↑ 　│ 所以 isSameGroup(2,1) 就是 ture, ignore (6,3) ! └─────┘ 以下略 中间的 link list 处理方法不难, 可以自己想想 :) -- 有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。 　存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你 　，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也 　是比较不容易被击倒的人。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.56 ※ 编辑: ledia 来自: 140.112.30.56 (03/23 13:48) ※ 编辑: ledia 来自: 140.112.30.56 (03/23 13:48)