A Huster

0%

Tarjan初步-点双连通分量

Posted on Edited on Valine:

上一次我们讲到了边双，这次我们来看点双。

说实话来说，点双比边双稍微复杂一些；

学完边双，我们先看一道题

alt

alt

第一问都不用说了吧，多余的道路，明显的割边。

是不是首先想到用边双，但是我们来看一个图：

alt**

有点丑，但是凑活看吧。

它是一个边双，但是！！！！它竟然没有冲突的边！！！

此时我们就要用点双了（是不是想打死我，竟然没讲，先坑人）

先看概念

alt

都说概念是非常重要的，但是概念似乎有点笼统，可以附图解说

alt

点双的一大特点是它可以重复用点，而那个点就是割点，而我们的缩点操作也是用割点连接各个点双的。

那么我们来看算法，我们在Tarjan时，用栈去维护点双，之后用vector去储存。

我们直接来看上面的题，就会明白这不是点双吗？

然后寻找规律，我们会发现，每一个点双中，只要边个数大于点个数，那么这里的边都是冲突的，那么我们的Code就跃然纸上了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define maxn 10007
#define M 100007
using namespace std;
int n,m,cent=1,t,head[maxn],low[maxn],dfn[maxn],ans1,ans2;
int stackk[maxn],cnt,top,root,cut[maxn],col[maxn],vis[maxn];
int ol;
vector<int >dcc[maxn];
struct node{
    int next,to;
}edge[M*2];

inline void add(int u,int v){
    edge[++cent]=(node){head[u],v};head[u]=cent;
}

void Tarjan(int x,int fa){
    dfn[x]=low[x]=++t;
    stackk[++top]=x;//入栈 
    if(x==root&&head[x]==0){//不联通时的孤立点 
        dcc[++cnt].push_back(x);
        return ;
    }
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!dfn[y]){
            Tarjan(y,i);
            low[x]=min(low[x],low[y]);//与其他的一样 
            if(low[y]>=dfn[x]){
                if(low[y]>dfn[x]) ans1++;//记录割边个数 
                int z;cnt++;
                do{
                    z=stackk[top--];//从栈中取出 
                    dcc[cnt].push_back(z);//存入 
                }while(z!=y);//停止条件，这个可以想一想为什么 
                dcc[cnt].push_back(x);//把割点也存进去 
            }
        }else if((i^1)!=fa) low[x]=min(low[x],dfn[y]);
    }
}

void clear(){
    ans1=ans2=top=cnt=t=ol=0;cent=1;
    memset(head,0,sizeof head);
    memset(low,0,sizeof low);
    memset(dfn,0,sizeof dfn);
    memset(stackk,0,sizeof stackk);
    memset(dcc,0,sizeof dcc);
    memset(col,0,sizeof col);
    memset(edge,0,sizeof edge);
}

int main(){
//    freopen("way.in","r",stdin);
//    freopen("way.out","w",stdout);
    while(scanf("%d%d",&n,&m)){
        if(n==0&&m==0)break;
        clear();
        int a,b;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            add(a+1,b+1),add(b+1,a+1);//由于点从零开始，那么我们+1即可 
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) root=i,Tarjan(i,-1);
        }
        for(int i=1;i<=cnt;i++,ol=0){
            for(int j=0;j<dcc[i].size();j++){
                vis[dcc[i][j]]=1;//记录点双上的点 
            }
            for(int k=0;k<dcc[i].size();k++){
                for(int j=head[dcc[i][k]];j;j=edge[j].next){
                    if(vis[edge[j].to]) ol++;//ol统计边数 
                }
            }
            if(ol/2>dcc[i].size()) ans2+=ol/2;//由于是双向边，ol会统计量词 
            memset(vis,0,sizeof(vis));
        }
        printf("%d %d\n",ans1,ans2);
    }
}

那么我们就应该懂了一些基本的概念，和简单的操作，那么，留一个彩蛋，我们该如何去缩点连接呢？

本站访问次数：