c*******t
发帖数: 123 | 1 问题是：
有一个村庄，很多人，有两种statement,
1. A's birth is after B's death.
2. A and B's lifetime have overlap.
find if there's any inconsistence.
第一条比较简单，找环，第二个条件如何应用呢？非常糊涂。望大侠指点。附上地里的
原帖地址：
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=14 | a*****a
发帖数: 46 | 2 有个思路，比如每个人A的lifetime用两个node来表示A0(birth) 和A1(death)， A0->
A1，用个有方向
的边表示出来前后关系，这样的话，条件1的表示就是B1->A0， 条件2表示出来就是A0-
>B1 and B0->A1,然后在这个图上找环。 | c*******t
发帖数: 123 | 3 太棒了！
我相信你是对的。
我思路和你类似，隐约觉得应该把第二个条件按起点和终点分开，做成有向图。
但思路没有继续下去，没想到第二个条件可以拆开成两个子条件。
太感谢了！
A0-
【在 a*****a 的大作中提到】
: 有个思路，比如每个人A的lifetime用两个node来表示A0(birth) 和A1(death)， A0->
: A1，用个有方向
: 的边表示出来前后关系，这样的话，条件1的表示就是B1->A0， 条件2表示出来就是A0-
: >B1 and B0->A1,然后在这个图上找环。
|
|
