它是什么？

对于一个无向图，如果它没有割点，则称其为“点双联通图”

无向图的极大点双连通子图成为“点双连通分量”

它可以用来做什么？

如果对无向图中的所有点双连通分量缩点，可以得到一颗树，可以比较方便地将一些路径问题转化为树上问题

怎么求？

我们可以在TarjanTarjan求割点时，顺便把所有v−DCCv-DCC求出来，流程如下:

  1. 当一个节点第一次被访问时，入栈
  2. 当dfn[x]≤low[v]dfn[x]\leq low[v]成立（即割点判定法则）时
    从弹栈，直至节点vv被弹出，所有弹出的节点与xx共同构成一个v−DCCv-DCC

缩点相对复杂一些这就是我一直不会写点双的原因其实好像也不是很难，因为一个割点可能属于多个v−DCCv-DCC

设图中一共有kk个割点，tt个v−DCCv-DCC，建立一张包含k+tk+t个节点的新图，把每个v−DCCv-DCC和割点作为新图中的节点，并在在每个割点和所有包含它的v−DCCv-DCC之间连边

最终获得的图即是一颗树（或是森林）

例题

BZOJ3331 压力

~~TLDR~~一句话题意：
给定nn个点mm条边的无向连通图，以及qq个点对
对于每个点对，它们的路径上有一些点是必经点（包括起点和终点）
对于图上的每个点，求出它们是多少个点对路径的必经点

Description

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的
核心路由器典型的要处理100Gbit/s100Gbit/s的网络流量。他们每天都生活在巨大的压力
之下。
小强建立了一个模型。这世界上有NN个网络设备,他们之间有M个双向的
链接。这个世界是连通的。在一段时间里,有QQ个数据包要从一个网络设备发
送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于QQ个数据包各自走
的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设
备。
你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有
多少个?

Input

第一行包含3个由空格隔开的正整数N,M,Q。
接下来M行,每行两个整数u,v,表示第u个网络设备(从1开始编号)和
第v个网络设备之间有一个链接。u不会等于v。两个网络设备之间可能有多个
链接。
接下来Q行,每行两个整数p,q,表示第p个网络设备向第q个网络设备发
送了一个数据包。p不会等于q。

Output

输出N行,每行1个整数,表示必须通过某个网络设备的数据包的数量。

Sample Input

4 4 2
1 2
1 3
2 3
1 4
4 2
4 3

Sample Output

2
1
1
2

HINT

【样例解释】
设备1,2,31,2,3之间两两有链接,44只和11有链接。44想向22和33各发送一个数据包。显然,这两个数据包必须要经过它的起点、终点和11。

【数据规模和约定】
对于40%40\%的数据,N,M,Q≤2000N,M,Q≤2000
对于60%60\%的数据,N,M,Q≤40000N,M,Q≤40000
对于100%100\%的数据,N≤100000,M,Q≤200000N≤100000,M,Q≤200000

Solution

显然对于原图的一个点，如果它不是割点，那么除了作为起点和和终点，它不会成为任何一条路径的必经点，否则它一定是经过它的路径的必经点

对原图求点双并进行缩点，获得一棵树，新图中的点只有割点和各个点双
对于非割点，统计它是多少条路径的起点和终点
对于割点，计算它被多少条路径覆盖，LCA求路径，树上差分即可
这样，我们就成功地把原问题转化为树上问题

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#define maxn 200005//不知道为什么，如果只开100000在BZOJ上会REemmmmm
#define maxm 200005
using namespace std;
typedef long long ll;

int n,m,q;
int ans[maxn],c[maxn];

struct edge
{
	int u,v,nxt;
}g[maxm*2];

int nn;//强连通分量编号
vector<int> dcc[maxn];//使用vector记录每个v-DCC所包含的节点

int head[maxn],ecnt;
void eADD(int u,int v)
{
	g[++ecnt].u=u;
	g[ecnt].v=v;
	g[ecnt].nxt=head[u];
	head[u]=ecnt;
}

int dfn[maxn],low[maxn],sign;
int stk[maxn],top;
int bel[maxn],cut[maxn];
int root;
void Tarjan(int u,int fa)
{
	dfn[u]=low[u]=++sign;
    if(u==root && head[u]==0)
    {
    	dcc[++nn].push_back(u);
        return;
    }//孤立点
	stk[++top]=u;
	int flag=0;
	for(register int i=head[u];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(v==fa)
			continue;
		if(!dfn[v])
		{
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				++flag;
				if(u!=root || flag>1)
					cut[u]=1;
				++nn;
				while(stk[top+1]!=v)
					dcc[nn].push_back(stk[top--]);
				dcc[nn].push_back(u);
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}

int prt[maxn][21],dep[maxn];
void dfs0(int u,int fa,int depth)
{
	prt[u][0]=fa;
	dep[u]=depth;
	for(register int i=1;(1<<i)<=depth;++i)
		prt[u][i]=prt[prt[u][i-1]][i-1];
	for(register int i=head[u];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(v!=fa)
			dfs0(v,u,depth+1);
	}
}

int LCA(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(register int i=20;i>=0;--i)
		if(dep[prt[x][i]]&gt;=dep[y])
			x=prt[x][i];
	if(x==y)
		return x;
	for(register int i=20;i>=0;--i)
		if(prt[x][i]!=prt[y][i])
		{
			x=prt[x][i];
			y=prt[y][i];
		}
	return prt[x][0];
}

void dfs1(int u,int fa)
{
	for(register int i=head[u];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(v!=fa)
		{
			dfs1(v,u);
			c[u]+=c[v];
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(register int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		eADD(u,v),eADD(v,u);
	}
	for(register int i=1;i<=n;++i)
		if(!dfn[i])
			Tarjan(root=i,0);
	int new_id=nn;
	for(register int i=1;i<=n;++i)
		if(cut[i])
			bel[i]=++new_id;//为每个割点分配单独的bel
	memset(g,0,sizeof(g));
	memset(head,0,sizeof(head));
	ecnt=0;//清空原图，建立新图
	for(register int i=1;i<=nn;++i)
		for(register int j=0;j<dcc[i].size();++j)
			if(cut[dcc[i][j]])
				eADD(bel[dcc[i][j]],i),eADD(i,bel[dcc[i][j]]);
			else
				bel[dcc[i][j]]=i;//非割点只会属于一个点双
	dfs0(1,0,1);
	while(q--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(bel[u]==bel[v])//特判
		{
			++ans[u],++ans[v];
			continue;
		}
		int lca=LCA(bel[u],bel[v]);
		++c[bel[u]],++c[bel[v]];
		if(!cut[u])++ans[u];//若为割点，则不需要单独增加答案
		if(!cut[v])++ans[v];
		c[lca]--,c[prt[lca][0]]--;//差分
	}
	dfs1(1,0);
	for(register int i=1;i<=n;++i)
	{
		if(cut[i])
			printf("%d\n",c[bel[i]]+ans[i]);
		else
			printf("%d\n",ans[i]);
	}
	return 0;
}