avatar
c*h
1
有很多pair,比如(a,b),(b,c),(a,c)。假设每个pair有依赖关系,a 依赖于b,b依赖
于c,a依赖于c。事实上(a,c)是多余的。现在要求剔除所有多余的pair。
现在只能想到构建个graph,然后找出所有loop,再断开它,接着遍历一篇。好像很复
杂,不知道有什么简单的方法来搞。。。
avatar
l*l
2
放hashtable里面不停的删除?
avatar
d*k
3
我说个暴利方法。
首先根据pair, 构建一个有向图。pair (a, b)代表一条从b到a的边。
对于每个pair (a, b), 删除边b->a,从b为起点做dfs,若a可达,则删除(a,b)。
时间复杂度为E*V,E为pair数,V为顶点数。
另一种方法
可以从每个顶点为起点遍历一次,例如做bfs,若对于每个位于层数大于1的节点,若有
起点到它的边,则删除。时间复杂度为V^2
avatar
g*o
4
多余的定义是什么?
比如
(a,b),(b,c),(a,d),(d,c)
里面有多余的吗?
这里面也有loop

【在 c*******h 的大作中提到】
: 有很多pair,比如(a,b),(b,c),(a,c)。假设每个pair有依赖关系,a 依赖于b,b依赖
: 于c,a依赖于c。事实上(a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph,然后找出所有loop,再断开它,接着遍历一篇。好像很复
: 杂,不知道有什么简单的方法来搞。。。

avatar
f*4
5
新增 x->y 时,检查y的直接前驱是否可达x,如果可达则删除该前驱
avatar
c*h
6
这里没有多余的,这样的pair是单向的。举个例子,(a,b),(b,c),(c,d),(d,e),(a,c)
,(b,e)里面,(a,c)和(b,e)是多余的。
avatar
l*n
7
应该是toposort的变体吧。
照toposort的算法走,先考虑入度为0的点,(a,b),(b,c),(c,d),(d,e),(a,c),(b,e)中
入读为0的点是a。a连接的是b和c,如果把a及其边删除,b的入度变为0,c的入度是1,
所以(a,c)就是多余的。
再比如(a,b),(b,c),(c,d),(d,e),(a,c),(a,e),即a跟b,c,e相连。a及其边删除后,b
,c,e的入度分别为0,1,1,所以(a,c), (a,e)都是多余的。
avatar
e*t
8
拓扑排序

【在 c*******h 的大作中提到】
: 有很多pair,比如(a,b),(b,c),(a,c)。假设每个pair有依赖关系,a 依赖于b,b依赖
: 于c,a依赖于c。事实上(a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph,然后找出所有loop,再断开它,接着遍历一篇。好像很复
: 杂,不知道有什么简单的方法来搞。。。

avatar
S*t
9
dfs做一遍,每个点存incoming edge, 如果第二次visit同一个点,前次存的次的edge
删掉并被替换为新的incoming edge

【在 c*******h 的大作中提到】
: 有很多pair,比如(a,b),(b,c),(a,c)。假设每个pair有依赖关系,a 依赖于b,b依赖
: 于c,a依赖于c。事实上(a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph,然后找出所有loop,再断开它,接着遍历一篇。好像很复
: 杂,不知道有什么简单的方法来搞。。。

avatar
c*h
10
想出来一个用hashtable + bfs的方法,用python写了一下。
from sets import Set
def create_pool(pool,maps,keys):
pool += keys
[ create_pool(pool, maps, maps[key]) for key in keys if maps.has_key(key
) ]
return pool
def findminimalpair(pairs):
keys = list(Set([item[0] for item in pairs ]))
maps = dict((key,[]) for key in keys)
for item in pairs:
maps[item[0]].append(item[1])
result = []
for key in keys:
values = maps[key]
pool = create_pool([],maps,[key])
pool.pop(0)
newvalues = [ val for val in values if pool.count(val)==1 ]
result += [(key,val) for val in newvalues]
return result
avatar
d*n
11
有没有更简单直接的解法呢?

key

【在 c*******h 的大作中提到】
: 想出来一个用hashtable + bfs的方法,用python写了一下。
: from sets import Set
: def create_pool(pool,maps,keys):
: pool += keys
: [ create_pool(pool, maps, maps[key]) for key in keys if maps.has_key(key
: ) ]
: return pool
: def findminimalpair(pairs):
: keys = list(Set([item[0] for item in pairs ]))
: maps = dict((key,[]) for key in keys)

avatar
b*e
12
Dijkstra求连通算法可解。在adjacent matrix上执行Dijkstra算法,如果某一个cell
的值为1且从未被改变过,那么这个cell所对应的edge是一个canonical edge。

【在 c*******h 的大作中提到】
: 有很多pair,比如(a,b),(b,c),(a,c)。假设每个pair有依赖关系,a 依赖于b,b依赖
: 于c,a依赖于c。事实上(a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph,然后找出所有loop,再断开它,接着遍历一篇。好像很复
: 杂,不知道有什么简单的方法来搞。。。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。