3310一开始打算拓扑排序但考虑到有环的存在也不是很好如果一个节点能够被指且不自成环那么可以认为是安全的否则若没有被指或者被指了且成环了那么删除由此节点延申出的一切节点先是判断是否被指若被指则检测指的那个节点是否在自己的环上若在则执行清除否则执行清除对于清除方法清除掉一切由此节点产生的节点给定一系列边关系后如何构建出来就是可达性维护一个vector,是当前可达的那些点对于新边先检测起点是否在数组中若在则可加入但这样会有问题若起点为O有边OA和AB若先遇到AB发现数组里还没A即O还不可达A那么也不会把B放入数组中但遇到OA后就可以了所以如何更好地去维护这个数组最笨的方法就是不断遍历每到一个新边就不断地去尝试之前没通过的边但这样可能会发生递归问题即遇到V1边遍历之前没成功的集合如果到最后才能成功V2的话可能在之前的集合里还有V3可以利用即每成功加入一条边就要去检测一次没成功的边集合对于这个fail数组成功匹配的位置不确定所以当发生擦除时可以是任意位置那么需要实现链表式的擦除也很费劲还有就是维护一个数组即是否有边的终点是该点最后检测这个数组里的所有点是否被可达若全都可以则删除对于BFS感觉也是会出现可能可达但提前检测导致被判定为不可达的情况即[AB][OA]情况这时候怎么处理才能不重不漏忘记先建图了
3310一开始打算拓扑排序但考虑到有环的存在也不是很好如果一个节点能够被指且不自成环那么可以认为是安全的否则若没有被指或者被指了且成环了那么删除由此节点延申出的一切节点先是判断是否被指若被指则检测指的那个节点是否在自己的环上若在则执行清除否则执行清除对于清除方法清除掉一切由此节点产生的节点给定一系列边关系后如何构建出来就是可达性维护一个vector,是当前可达的那些点对于新边先检测起点是否在数组中若在则可加入但这样会有问题若起点为O有边OA和AB若先遇到AB发现数组里还没A即O还不可达A那么也不会把B放入数组中但遇到OA后就可以了所以如何更好地去维护这个数组最笨的方法就是不断遍历每到一个新边就不断地去尝试之前没通过的边但这样可能会发生递归问题即遇到V1边遍历之前没成功的集合如果到最后才能成功V2的话可能在之前的集合里还有V3可以利用即每成功加入一条边就要去检测一次没成功的边集合对于这个fail数组成功匹配的位置不确定所以当发生擦除时可以是任意位置那么需要实现链表式的擦除也很费劲还有就是维护一个数组即是否有边的终点是该点最后检测这个数组里的所有点是否被可达若全都可以则删除对于BFS感觉也是会出现可能可达但提前检测导致被判定为不可达的情况即[AB][OA]情况这时候怎么处理才能不重不漏忘记先建图了
)
