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
|