C******x
发帖数: 91 | 1 有一个村庄，流传着两种statement：
1. A 死了之后 B出生。
2. A和B有overlap。
现在有很多这样的statements，要你判断有没有inconsistency.
应该是个图相关的题，拆点建图，但是第二个条件实在是不住到怎么建模。overlap有
四种情况，只能backtracking每个都试一遍吗？ |
h*****u
发帖数: 109 | 2 Base on 1, make a graph.
Put 2 in to hash, say HashSet in Java or unordered_set in C++
Do a depth-first traversal on the graph. If there is a cycle,
inconsistent due to condition 1.
Then, check condition 2.
For each pair of A and B,
check if both of them belong to any same component.
If so, return inconsistent.
return consistent. |
S********t
发帖数: 3431 | 3 我觉得你handle第二种statement不对。
a->c
b->c
abc都是connected(按我的理解，你是想用union find去记录connected components)，
但是a可以跟b有overlap。
最优解应该是加a->b edge后重新validate DAG，然后再加b->a后再validate一次。
【在 h*****u 的大作中提到】
: Base on 1, make a graph.
: Put 2 in to hash, say HashSet in Java or unordered_set in C++
: Do a depth-first traversal on the graph. If there is a cycle,
: inconsistent due to condition 1.
: Then, check condition 2.
: For each pair of A and B,
: check if both of them belong to any same component.
: If so, return inconsistent.
: return consistent.
|
h*****u
发帖数: 109 | 4 Right!
The key is at the path, no overlap.
【在 S********t 的大作中提到】
: 我觉得你handle第二种statement不对。
: a->c
: b->c
: abc都是connected(按我的理解，你是想用union find去记录connected components)，
: 但是a可以跟b有overlap。
: 最优解应该是加a->b edge后重新validate DAG，然后再加b->a后再validate一次。
|
m****v
发帖数: 780 | 5 这是G的题吗？还是你在网上找的传言是g的题？
【在 C******x 的大作中提到】
: 有一个村庄，流传着两种statement：
: 1. A 死了之后 B出生。
: 2. A和B有overlap。
: 现在有很多这样的statements，要你判断有没有inconsistency.
: 应该是个图相关的题，拆点建图，但是第二个条件实在是不住到怎么建模。overlap有
: 四种情况，只能backtracking每个都试一遍吗？
|
C******x
发帖数: 91 | 6 面经题 可以搜到的。
【在 m****v 的大作中提到】
: 这是G的题吗？还是你在网上找的传言是g的题？
|
C******x
发帖数: 91 | 7 I didn't get your idea exactly,
for the graph, what is the vertex and edge?
for the hash, what is the key, what is the value?
and, how is the component defined?
Thanks!
【在 h*****u 的大作中提到】
: Base on 1, make a graph.
: Put 2 in to hash, say HashSet in Java or unordered_set in C++
: Do a depth-first traversal on the graph. If there is a cycle,
: inconsistent due to condition 1.
: Then, check condition 2.
: For each pair of A and B,
: check if both of them belong to any same component.
: If so, return inconsistent.
: return consistent.
|
w***w
发帖数: 84 | 8 你把每个人分成起始两个点 起指向始 然后分情况加边 判断无回路即可 |
C******x
发帖数: 91 | 9 问题是第二个条件怎么加边 对于overlap 有四种case，那需要判断 4^|E| 个图中是否
有环，复杂度 看起来问题本身的复杂度就是这么高了 还请指点。
【在 w***w 的大作中提到】
: 你把每个人分成起始两个点 起指向始 然后分情况加边 判断无回路即可
|
w***w
发帖数: 84 | 10 加上 起点A至终点B 及 起点B至终点A 即可 |
h*****u
发帖数: 109 | 11 感觉这题很难做到 Complexity O(n)。主要是condition 1 is strong, but condition
2 is weak. 就是如果 "2. A和B有overlap"不能说明那个在前面。
所以graph只能以condition 1 build, 然后
1: 到cycle (inconsistent for sure),
2: 或者leaf node。这时候需要store the whole path, 比如tree path max sum这
种题.
for each node at the path
for each later node at the path
check if the node pair in condition 2.
If so, return inconsistent.
n^2
这是我能想到的。抛砖引玉。
【在 S********t 的大作中提到】
: 我觉得你handle第二种statement不对。
: a->c
: b->c
: abc都是connected(按我的理解，你是想用union find去记录connected components)，
: 但是a可以跟b有overlap。
: 最优解应该是加a->b edge后重新validate DAG，然后再加b->a后再validate一次。
|
