我有一个图表,从一个根节点开始.节点逐个添加到图表中.在节点创建时,它们必须通过单个边链接到根节点或另一个节点.也可以创建和删除边缘(在任意两个节点之间逐个删除).可以一次删除一个节点.节点和边创建,删除操作可以以任意顺序发生.
好的,所以这里是我的问题:当删除边缘时,是否可以在恒定时间内(即使用O(1)算法)确定,如果这样做会将图形分成两个不相交的子图形？如果是,那么根节点属于哪一边？
我愿意在合理的限度内维护任何可以促进此信息推导的附加数据结构.
也许在O(1)中不可能这样做,如果是这样的话,任何指向文学的人都会受到赞赏.
编辑:图表是有向图.
编辑2:好的,也许我可以限制从根节点删除边缘的情况.[编辑3:不,实际上]此外,没有边缘落入根节点.