白书上的所谓点连通模版似乎只有割点用用。。
binshen的板子：
int n, m;//n个点 m条无向边
#define N 20100
#define M 1000006
//点标从0开始
int head[N],edgenum;
int low[N], dfn[N], Stack[N<<1], top, instack[N],add_block[N],indexx,iscut[N], block_cnt; //block_cnt为图的连通分量数
struct Edge
{
int from, to, next;
}edge[M<<1];
void add(int u,int v)
{
Edge E = {u,v,head[u]};
edge[edgenum] = E;
head[u]=edgenum++;
}
void tarjin(int u,int pre)
{
int i, v;
low[u] = dfn[u] = ++indexx;
Stack[top++] = u;
int son = 0;
for(i = head[u]; ~i; i = edge[i].next)
{
v = edge[i].to;
if(v == pre)continue;
if(!dfn[v])
{
son++;
tarjin(v, u);
if(low[u]>low[v])low[u]=low[v];
if(u!=pre&&low[v]>=dfn[u])
{
iscut[u]=true;
add_block[u]++;
}
}
else if(low[u]>dfn[v])low[u]=dfn[v];
}
if(u==pre)add_block[u]=son-1;
if(u==pre&&son>1)iscut[u]=true;
//top--;
}
void find_bcc(int n){
memset(dfn, 0, sizeof(dfn));
memset(instack, 0, sizeof(instack));
memset(add_block, 0, sizeof(add_block));
memset(iscut, 0, sizeof(iscut));
indexx = top = 0;
block_cnt = 0; //连通分量数
for(int i = 0; i < n; i++)if(!dfn[i]) tarjin(i, i), block_cnt++;
}
板子2：
#define N 10010
struct Edge{
int from, to, nex;
bool cut;
}edge[100001*2];
int head[N], edgenum;
int bridgetop;
void addedge(int u, int v){
Edge E={u,v,head[u],false};
edge[ edgenum ] = E;
head[u] = edgenum++;
}
int n, m;
int dfn[N], low[N], tarjan_time, tar, Stack[N], top;
int Belong[N];
bool iscut[N];
void tarjan(int u, int fa){
dfn[u] = low[u] = ++tarjan_time;
Stack[++top] = u;
int child = 0, flag = 1;
for(int i = head[u]; ~i; i = edge[i].nex)
{
int v = edge[i].to;
if(flag && v==fa){flag = 0; continue;}
if(!dfn[v])
{
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u])
{
iscut[u] = true;
if(low[v]>dfn[u])
edge[i].cut = edge[i^1].cut = true;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(child == 1 && fa<0)iscut[u] = false;
if(low[u] == dfn[u])
{
tar++;
do
{
Belong[ Stack[top] ] = tar;
}while(Stack[top--] != u);
}
}
void init(){
memset(head, -1, sizeof(head)), edgenum = 0;
memset(dfn, 0, sizeof(dfn));
memset(iscut, 0, sizeof(iscut));
memset(Belong, -1, sizeof(Belong));
bridgetop = 0;
tarjan_time = 0;
top = 0;
tar = 0;
}