关于无向图缩点

最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz

我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所有点都缩进去了,很是恼火...

一开始遇到了,想了半小时,算了,放弃.直到最近水P2783的时候,突然恍然大悟,下面来介绍下我的做法(不知道有没有大佬跟我一样。。。)

首先,我们想,如果我们的无向图不是无向图而是有向图该多好啊。。。于是,我便打算只建一条边,然鹅这个想法很快就被淘汰了,因为,只建一条边后,图可能就不连通了啊！

要是,他一开始给的顺序是有序的就好了。。。(这里的有序是指连接顺序按照一定的规律),当然,这是不可能的!

突然,我灵机一动,既然如此,为什么我们不让这条无向边发挥它建图的作用后就让他失效呢？于是就有了我的无向tarjan初型:假设我们tarjan时,访问了一条u->v的边,我们就访问v的边,直到找到一条边为v->u,我们把它标记一下(我是前向星存边,故直接标记他的标号),下次我们访问到一条被标记的边时,我们不进行任何操作,直接跳过,就相当于一个有向图了~

然鹅...T到飞起~

原因出在哪里呢？其实,我们每次访问一条没有被标记的边时,都会花上连接它的目标点(即v)边的条数的运行次数访问,这是极其不优的,当然,由于我学了网络流的dinic算法,我很快想到了一条边及其反向边的关系:当我们存边是从一个偶数开始标号,且建立一条边后马上建立它的反向边,那么,设其中一条边的编号为i,则他的反向边的编号为(i^1),于是,我们就可以O(1)删边了~美哉美哉！