点双连通分量

对于无向图，如果删掉它的任意一个结点，整个图仍连通，图是点双连通图。

如果图的子图是点双连通图，则是的点双连通分量。

同一个点可能属于多个点双连通分量，但一条边只属于一个点双连通分量。

可以在 Tarjan 求割点的时候顺便求点双连通分量。

割点的邻边中必有割边，但邻边有割边的点不一定是割点。

圆方树

求出原图的所有极大点双连通分量，并给每个分量新建一个结点（方点），这个分量的其他点都连接这个方点。容易证明这样构造的结构是一个树形结构（因为有环的话可以合并成一个大的点双），称其为圆方树。

显然，圆方树可以在 Tarjan 求点双的过程中构建。

简单的性质

圆方树上度数大于 1 的圆点是割点。

例题

给定个点条边的无向图, 每次操作将之间所有必须经过的点权值加一，求操作完了之后每个点的权值。。

显然，建出圆方树后就是树上的一条路径，则树上差分即可。

由于是例题因此给出完整代码

#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=5e5+5,M=N;

struct qxx{int nex,t;};
qxx e[M];
int h[N],le=1;
void add_path(int f,int t){e[++le]=(qxx){h[f],t},h[f]=le;}

int n,m,q;

int dfn[N],low[N],totdfn;
int s[N],tp;
int vcc;
namespace G{
    qxx G_e[N*2];
    int G_h[M*2],G_le=1;
    int dep[N*2],fa[N*2][20],val[N*2];
    void G_add_path(int f,int t){G_e[++G_le]=(qxx){G_h[f],t},G_h[f]=G_le;}
    void G_add_both(int f,int t){G_add_path(f,t),G_add_path(t,f);}
    void dfs(int u,int p){
        dep[u]=dep[p]+1,fa[u][0]=p;
        FOR(i,1,19){
            fa[u][i]=fa[fa[u][i-1]][i-1];
            if(!fa[u][i])break;
        }
        for(int i=G_h[u];i;i=G_e[i].nex){
            const int v=G_e[i].t;
            if(v!=p)dfs(v,u);
        }
    }
    void make(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        int u1=u,v1=v;
        ROF(i,19,0) if(dep[u]-(1<<i)>dep[v])u=fa[u][i];
        if(fa[u][0]==v)return val[u1]++,val[fa[v][0]]--,void();
        if(dep[u]>dep[v])u=fa[u][0];
        ROF(i,19,0) if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
        u=fa[u][0];
        val[u1]++,val[v1]++,val[u]--,val[fa[u][0]]--;
    }
    void dfs2(int u,int p){
        for(int i=G_h[u];i;i=G_e[i].nex){
            const int v=G_e[i].t;
            if(v==p)continue;
            dfs2(v,u);
            val[u]+=val[v];
        }
    }
}
void tarjan(int u,int p){
    dfn[u]=low[u]=++totdfn;
    s[++tp]=u;
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                ++vcc, G::G_add_both(u,vcc+n);
                do { G::G_add_both(s[tp],vcc+n); }while(s[tp--]!=v);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    FOR(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        add_path(u,v);
        add_path(v,u);
    }
    tarjan(1,0);
    G::dfs(1,0);
    FOR(i,1,q){
        int u,v;
        scanf("%d%d",&u,&v);
        G::make(u,v);
    }
    G::dfs2(1,0);
    FOR(i,1,n)printf("%d\n",G::val[i]);
    return 0;
}