p*u
发帖数: 136 | 1 输入：
有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)的 |
l*********8
发帖数: 4642 | 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去解的正确性。
|
p*u
发帖数: 136 | 3 敲错了。敌人的敌人是朋友
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
|
d**********x
发帖数: 4083 | 4 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 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
|
d**********x
发帖数: 4083 | 5 ...
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
|
d**********x
发帖数: 4083 | 6 then what about... just union all connected friends, then do a bi-partition?
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
|
l*n
发帖数: 529 | 7 考虑了下，是不是可以用两层的并查集啊？先确定是否有关系，然后看是朋友还是敌人。
【在 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
发帖数: 2 | 8 有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。 |
s**x
发帖数: 7506 | |
l**********o
发帖数: 260 | 10 Nice!
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
|
|
|
f*********d
发帖数: 140 | |
z****e
发帖数: 54598 | 12 随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了 |
p*u
发帖数: 136 | 13 输入：
有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
发帖数: 4642 | 14 "敌人的敌人是敌人" ??
为什么敌人的敌人不是朋友？
如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
【在 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
发帖数: 136 | 15 敲错了。敌人的敌人是朋友
【在 l*********8 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
|
d**********x
发帖数: 4083 | 16 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 的大作中提到】
: "敌人的敌人是敌人" ??
: 为什么敌人的敌人不是朋友？
: 如果"敌人的敌人是敌人" 。 那么就是两个并查集 --- 朋友并查集， 敌人并查集。
|
d**********x
发帖数: 4083 | 17 ...
ouch
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
|
d**********x
发帖数: 4083 | 18 then what about... just union all connected friends, then do a bi-partition?
【在 p*u 的大作中提到】
: 敲错了。敌人的敌人是朋友
|
l*n
发帖数: 529 | 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去解的正确性。
|
c*******0
发帖数: 2 | 20 有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。 |
|
|
s**x
发帖数: 7506 | |
l**********o
发帖数: 260 | 22 Nice!
★ 发自iPhone App: ChineseWeb 7.8
【在 s**x 的大作中提到】
: http://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
: Not clear the details yet.
|
f*********d
发帖数: 140 | |
z****e
发帖数: 54598 | 24 随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了 |
s*****n
发帖数: 994 | 25 用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去解的正确性。
|
n*****f
发帖数: 17 | 26 这题是并查集的经典题，在基本并查集的基础上再多记一个变量，记该节点到这个集合
根结点的关系，比如0是同类，1是敌人。
这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
http://poj.org/problem?id=1182 |
z****s
发帖数: 409 | 27 这是并查集非常经典的题了。
说什么graph的真是菜的可以了，我就不明白了，你们就这水平怎么好意思在版上说话？
就算菜不是你的错，但你老么实的潜水就行了，别整天胡说八道。 |
r**********o
发帖数: 50 | 28 求具体细节：
如果是用TreeNode建树的话，是不是比较费空间？
还是用HashMap好点？ |
q****m
发帖数: 177 | 29 看第一个人，对他做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去解的正确性。
|
A*********c
发帖数: 430 | 30 赞。原题貌似是UVa 10158 - War？
【在 n*****f 的大作中提到】
: 这题是并查集的经典题，在基本并查集的基础上再多记一个变量，记该节点到这个集合
: 根结点的关系，比如0是同类，1是敌人。
: 这个题还可以扩展到超过2种的关系，比如POJ上食物链这道题。
: http://poj.org/problem?id=1182
|
