c*******h
发帖数: 22 | 1 有很多pair，比如（a,b),(b,c),(a,c)。假设每个pair有依赖关系，a 依赖于b，b依赖
于c，a依赖于c。事实上（a,c)是多余的。现在要求剔除所有多余的pair。
现在只能想到构建个graph，然后找出所有loop，再断开它，接着遍历一篇。好像很复
杂，不知道有什么简单的方法来搞。。。 | l******l
发帖数: 1088 | | d*k
发帖数: 207 | 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 | g****o
发帖数: 547 | 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，再断开它，接着遍历一篇。好像很复
: 杂，不知道有什么简单的方法来搞。。。
| f*******4
发帖数: 64 | 5 新增 x->y 时，检查y的直接前驱是否可达x，如果可达则删除该前驱 | c*******h
发帖数: 22 | 6 这里没有多余的，这样的pair是单向的。举个例子，（a,b),(b,c),(c,d),(d,e),(a,c)
,(b,e)里面，(a,c)和（b,e)是多余的。 | l*n
发帖数: 529 | 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)都是多余的。 | e*****t
发帖数: 1005 | 8 拓扑排序
【在 c*******h 的大作中提到】
: 有很多pair，比如（a,b),(b,c),(a,c)。假设每个pair有依赖关系，a 依赖于b，b依赖
: 于c，a依赖于c。事实上（a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph，然后找出所有loop，再断开它，接着遍历一篇。好像很复
: 杂，不知道有什么简单的方法来搞。。。
| S********t
发帖数: 3431 | 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，再断开它，接着遍历一篇。好像很复
: 杂，不知道有什么简单的方法来搞。。。
| c*******h
发帖数: 22 | 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 | d****n
发帖数: 233 | 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)
| b***e
发帖数: 1419 | 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，再断开它，接着遍历一篇。好像很复
: 杂，不知道有什么简单的方法来搞。。。
|
|
