p*u
2 楼
输入：
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的
J*S
3 楼
没有小孩，没有老人。
看到几个好像中年的男人，中年的妇女。
这是个什么样的家庭呢？
看到几个好像中年的男人，中年的妇女。
这是个什么样的家庭呢？
w*o
4 楼
是哦，不管是谁，把这事牵扯到女教授身上，也太缺德了。我要是那女AP，就跟男猪脚
说，你不把这bt老婆踹了，我就不让你毕业。
【在 G*****7 的大作中提到】
: 搞的她把lab主页都撤了
: 男猪是shen前学生还是现学生来着？
说，你不把这bt老婆踹了，我就不让你毕业。
【在 G*****7 的大作中提到】
: 搞的她把lab主页都撤了
: 男猪是shen前学生还是现学生来着？
l*8
5 楼
"敌人的敌人是敌人" ??
为什么敌人的敌人不是朋友？
如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
为什么敌人的敌人不是朋友？
如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
u*q
6 楼
幸福的家庭。
m*a
7 楼
这对师姐师弟的 financial support (RA) 成问题了。
【在 G*****7 的大作中提到】
: 搞的她把lab主页都撤了
: 男猪是shen前学生还是现学生来着？
【在 G*****7 的大作中提到】
: 搞的她把lab主页都撤了
: 男猪是shen前学生还是现学生来着？
p*u
8 楼
敲错了。敌人的敌人是朋友
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
N*m
9 楼
几个？
【在 J**S 的大作中提到】
: 没有小孩，没有老人。
: 看到几个好像中年的男人，中年的妇女。
: 这是个什么样的家庭呢？
【在 J**S 的大作中提到】
: 没有小孩，没有老人。
: 看到几个好像中年的男人，中年的妇女。
: 这是个什么样的家庭呢？
w*o
10 楼
以后招学生，如果是已婚的，要评估一下其配偶的精神状况再招。
【在 m****a 的大作中提到】
: 这对师姐师弟的 financial support (RA) 成问题了。
【在 m****a 的大作中提到】
: 这对师姐师弟的 financial support (RA) 成问题了。
d*x
11 楼
i think it's more likely connected components (not really).
you need multiple union sets because if 2 people are not in the same set,
they may have no relation --
that makes things much easier. we can first union people into groups, then
if 2 groups are directly connected, people inside these 2 groups are enemies
to each other. people belong to the same group are friends to each other.
and in other cases, they do not have any relations.
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
you need multiple union sets because if 2 people are not in the same set,
they may have no relation --
that makes things much easier. we can first union people into groups, then
if 2 groups are directly connected, people inside these 2 groups are enemies
to each other. people belong to the same group are friends to each other.
and in other cases, they do not have any relations.
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
j*i
12 楼
安徽某县县长？
m*a
13 楼
不在于已婚还是未婚， 给的活太少了， 闲的。
【在 w**o 的大作中提到】
: 以后招学生，如果是已婚的，要评估一下其配偶的精神状况再招。
【在 w**o 的大作中提到】
: 以后招学生，如果是已婚的，要评估一下其配偶的精神状况再招。
d*x
14 楼
...
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
s*o
15 楼
COMMUNITY啊，天天ORGY？
G*7
16 楼
怎么我记得是湿地觉得shen push，湿姐做好人把湿地转到另一个老板门下？
难道湿地石阶都是shen的current student？
【在 m****a 的大作中提到】
: 这对师姐师弟的 financial support (RA) 成问题了。
难道湿地石阶都是shen的current student？
【在 m****a 的大作中提到】
: 这对师姐师弟的 financial support (RA) 成问题了。
d*x
17 楼
then what about... just union all connected friends, then do a bi-partition?
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
p*p
18 楼
赶紧装个摄像头，对准邻居，研究一下
l*n
19 楼
考虑了下，是不是可以用两层的并查集啊？先确定是否有关系，然后看是朋友还是敌人。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
p*g
20 楼
我们家附近，有人买了房子，回国，转手出租了，家里也是这么住了几个年轻男女。后
来（听邻居说）发现这伙人居然在一起吸毒，到处乱停车，其他的问题不知道。
最后警察要求他们搬走，搬走的时候，城市的swat都来了，那天起码是5辆警车在门口
当时还想怎么这么奇怪，晚上睡不着，门口走一下，马上警车不知道从那里开过来就停
你边上，也不打搅你，就是让你感觉不舒服，还以为有人没事盯着我
BTW，我们这里属于治安不错的地方
来（听邻居说）发现这伙人居然在一起吸毒，到处乱停车，其他的问题不知道。
最后警察要求他们搬走，搬走的时候，城市的swat都来了，那天起码是5辆警车在门口
当时还想怎么这么奇怪，晚上睡不着，门口走一下，马上警车不知道从那里开过来就停
你边上，也不打搅你，就是让你感觉不舒服，还以为有人没事盯着我
BTW，我们这里属于治安不错的地方
c*0
21 楼
有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。
u*q
22 楼
BSO警察昼夜保护。
【在 p**********g 的大作中提到】
: 我们家附近，有人买了房子，回国，转手出租了，家里也是这么住了几个年轻男女。后
: 来（听邻居说）发现这伙人居然在一起吸毒，到处乱停车，其他的问题不知道。
: 最后警察要求他们搬走，搬走的时候，城市的swat都来了，那天起码是5辆警车在门口
: 当时还想怎么这么奇怪，晚上睡不着，门口走一下，马上警车不知道从那里开过来就停
: 你边上，也不打搅你，就是让你感觉不舒服，还以为有人没事盯着我
: BTW，我们这里属于治安不错的地方
【在 p**********g 的大作中提到】
: 我们家附近，有人买了房子，回国，转手出租了，家里也是这么住了几个年轻男女。后
: 来（听邻居说）发现这伙人居然在一起吸毒，到处乱停车，其他的问题不知道。
: 最后警察要求他们搬走，搬走的时候，城市的swat都来了，那天起码是5辆警车在门口
: 当时还想怎么这么奇怪，晚上睡不着，门口走一下，马上警车不知道从那里开过来就停
: 你边上，也不打搅你，就是让你感觉不舒服，还以为有人没事盯着我
: BTW，我们这里属于治安不错的地方
s*x
23 楼
http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
Not clear the details yet.
Not clear the details yet.
p*g
24 楼
那些人搬走以后，警察就不出现了
【在 u****q 的大作中提到】
: BSO警察昼夜保护。
【在 u****q 的大作中提到】
: BSO警察昼夜保护。
l*o
25 楼
Nice!
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
m*y
26 楼
丁克吧。
不过，据说人的生物钟会自然产生抚育幼崽的冲动，到中年后会越来越强。不是滥用毒
品的，都顶不住这种生物性，所以，你会看到好多老美，即使自己不能／愿生，也要领
养。
所以，真正的丁克，除了少数天然钟烂了的，都是滥用毒品的。滥用毒品的滥交也很正
常。
不过，据说人的生物钟会自然产生抚育幼崽的冲动，到中年后会越来越强。不是滥用毒
品的，都顶不住这种生物性，所以，你会看到好多老美，即使自己不能／愿生，也要领
养。
所以，真正的丁克，除了少数天然钟烂了的，都是滥用毒品的。滥用毒品的滥交也很正
常。
f*d
27 楼
用并査集分集合
然后二着色
然后二着色
z*e
28 楼
随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了
p*u
29 楼
输入：
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的
==========
update一下，最后给了onsite，赞国人面试官！
有n个人，m条关系（a, b, enemy/friend）
有2个性质：
1，朋友的朋友是朋友
2，敌人的敌人是朋友
输入不会自相矛盾。
有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
最终时间复杂度是O(n^3)的。
华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
希望能过 :-)
------
这个问题的变形：
有很重要的条件：敌人的朋友是什么？朋友的敌人是什么？
但是题目中没有给。如果敌人的朋友或者朋友的敌人都是敌人的话，问题就简化了。以
每个节点作为起点，去做一次dfs，记录到当前节点经过了多少个敌人关系的边。奇数
个为敌人，偶数个为朋友。
最后时间复杂度是O(n^2)的
------
另外如果没有敌人这一说，只有朋友的话，就是并查集的做法。时间复杂度是O(n)的
==========
update一下，最后给了onsite，赞国人面试官！
l*8
30 楼
"敌人的敌人是敌人" ??
为什么敌人的敌人不是朋友？
如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
为什么敌人的敌人不是朋友？
如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
p*u
31 楼
敲错了。敌人的敌人是朋友
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
d*x
32 楼
i think it's more likely connected components (not really).
you need multiple union sets because if 2 people are not in the same set,
they may have no relation --
that makes things much easier. we can first union people into groups, then
if 2 groups are directly connected, people inside these 2 groups are enemies
to each other. people belong to the same group are friends to each other.
and in other cases, they do not have any relations.
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
you need multiple union sets because if 2 people are not in the same set,
they may have no relation --
that makes things much easier. we can first union people into groups, then
if 2 groups are directly connected, people inside these 2 groups are enemies
to each other. people belong to the same group are friends to each other.
and in other cases, they do not have any relations.
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
d*x
33 楼
...
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
d*x
34 楼
then what about... just union all connected friends, then do a bi-partition?
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
l*n
35 楼
考虑了下，是不是可以用两层的并查集啊？先确定是否有关系，然后看是朋友还是敌人。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
c*0
36 楼
有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。
s*x
37 楼
http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
Not clear the details yet.
Not clear the details yet.
l*o
38 楼
Nice!
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
f*d
39 楼
用并査集分集合
然后二着色
然后二着色
z*e
40 楼
随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了
s*n
41 楼
用graph来解
red edge is friend
black edge is enemy
no edge means no relation
遍历所有m条edge
if (red),调用addRedEdge：对two end nodes的每一条red edge的另一点call
addRedEdge
if (black),调用addBlackEdge：对two end nodes的每一条black edge的另一点call
addRedEdge
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
red edge is friend
black edge is enemy
no edge means no relation
遍历所有m条edge
if (red),调用addRedEdge：对two end nodes的每一条red edge的另一点call
addRedEdge
if (black),调用addBlackEdge：对two end nodes的每一条black edge的另一点call
addRedEdge
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
n*f
42 楼
这题是并查集的经典题，在基本并查集的基础上再多记一个变量，记该节点到这个集合
根结点的关系，比如0是同类，1是敌人。
这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
http://poj.org/problem?id=1182
根结点的关系，比如0是同类，1是敌人。
这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
http://poj.org/problem?id=1182
z*s
43 楼
这是并查集非常经典的题了。
说什么graph的真是菜的可以了，我就不明白了，你们就这水平怎么好意思在版上说话？
就算菜不是你的错，但你老么实的潜水就行了，别整天胡说八道。
说什么graph的真是菜的可以了，我就不明白了，你们就这水平怎么好意思在版上说话？
就算菜不是你的错，但你老么实的潜水就行了，别整天胡说八道。
r*o
44 楼
求具体细节：
如果是用TreeNode建树的话，是不是比较费空间？
还是用HashMap好点？
如果是用TreeNode建树的话，是不是比较费空间？
还是用HashMap好点？
q*m
45 楼
看第一个人，对他做dfs,可以找出这个人所在的connected component, 以及这个人和
component里面其他所有人的关系。这个component 里面其他人互相之间的关系可以通
过他们和第一个人之间的关系得出。
dfs 是O(n),但是确定两两的关系是O(n^2)
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
component里面其他所有人的关系。这个component 里面其他人互相之间的关系可以通
过他们和第一个人之间的关系得出。
dfs 是O(n),但是确定两两的关系是O(n^2)
【在 p*u 的大作中提到】
: 输入：
: 有n个人，m条关系（a, b, enemy/friend）
: 有2个性质：
: 1，朋友的朋友是朋友
: 2，敌人的敌人是朋友
: 输入不会自相矛盾。
: 有x个查询，每次查询(a, b)到底是什么关系？没关系，敌人或朋友
: 我是用类似floyd的思路去解的。f[a][b] = -1没关系, 0朋友, 1敌人
: 最终时间复杂度是O(n^3)的。
: 华人面试官，人不错挺有耐心的，超时了20分钟，讨论用floyd去解的正确性。
A*c
46 楼
赞。原题貌似是UVa 10158 - War？
【在 n*****f 的大作中提到】
: 这题是并查集的经典题，在基本并查集的基础上再多记一个变量，记该节点到这个集合
: 根结点的关系，比如0是同类，1是敌人。
: 这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
: http://poj.org/problem?id=1182
【在 n*****f 的大作中提到】
: 这题是并查集的经典题，在基本并查集的基础上再多记一个变量，记该节点到这个集合
: 根结点的关系，比如0是同类，1是敌人。
: 这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
: http://poj.org/problem?id=1182
相关阅读
以前大家说的那个离modem较远的可以用来提高网络信号的东西叫什么？求救，小竹子夹杂在花，树的根部请问现在市面上买得到的燃气炉都有灭火保护吗？神器二怎么自己开和变速求推荐在湾区的修slab concrete foundation的contractor换了个马桶，挫折感很强关于Appraisal做一个小统计死呆婆居然卖漏的打折GC房子有烟味springkler system 有一个zone的喷头不受控制，一直开着，什么原因？请教关于home security系统的选择地下室厕所排水的问题纯理论讨论啊，付清的出租房一定要买保险么？请问 zillow上的lender 可信么10万收入能买多少钱的房子“预防牙结石、去除牙渍”这样的牙膏用了会中毒砍树估价亏五万了，还是卖不掉房子冰箱断电后又工作了是什么原因？Location vs floor plan，鱼与熊掌不可兼得？