Tarjan的三大应用之一:求解点双联通分量。
求解点双联通分量。然后缩点,差分优化即可。
//BZOJ 3331 //by Cydiater //2016.10.29 #include <iostream> #include <cmath> #include <cstdlib> #include <cstdio> #include <queue> #include <map> #include <cstring> #include <string> #include <algorithm> #include <set> #include <bitset> #include <iomanip> #include <ctime> #include <vector> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) #define Auto(i,a) for(int i=LINK[a];i;i=e[i].next) #define vci vector<int> #define pb push_back const int MAXN=4e5+5; const int oo=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int N,M,Q,lable[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],top=0,dfs_clock=0,fa[MAXN][25],dep[MAXN],group_num=0; vci group[MAXN]; struct edge{int x,y,next;}; struct Graph{ int LINK[MAXN],len; Graph(){memset(LINK,0,sizeof(LINK));len=0;} edge e[MAXN]; inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;} inline void Insert(int x,int y){insert(x,y);insert(y,x);} void tarjan(int node){ dfn[node]=low[node]=++dfs_clock; stack[++top]=node;int son=0; Auto(i,node)if(!dfn[e[i].y]){ tarjan(e[i].y); cmin(low[node],low[e[i].y]); if(low[e[i].y]>=dfn[node]){ int tmp;group_num++; do{ tmp=stack[top--]; group[group_num].pb(tmp); }while(tmp!=e[i].y); group[group_num].pb(node); } }else cmin(low[node],dfn[e[i].y]); } void dfs(int node,int deep,int father){ fa[node][0]=father;dep[node]=deep; Auto(i,node)if(e[i].y!=father)dfs(e[i].y,deep+1,node); } void get_ancestor(){ up(i,1,20)up(node,1,N+group_num)if(fa[node][i-1]) fa[node][i]=fa[fa[node][i-1]][i-1]; } int LCA(int x,int y){ if(x==y) return x; if(dep[x]<dep[y])swap(x,y); down(i,20,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i]; if(x==y) return x; down(i,20,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){ x=fa[x][i];y=fa[y][i]; } return fa[x][0]; } void re_dfs(int node){ Auto(i,node)if(e[i].y!=fa[node][0]){ re_dfs(e[i].y); lable[node]+=lable[e[i].y]; } } }G1,G2; namespace solution{ void init(){ N=read();M=read();Q=read(); up(i,1,M){ int x=read(),y=read(); G1.Insert(x,y); } } void slove(){ G1.tarjan(1); up(i,1,group_num)up(j,0,group[i].size()-1)G2.Insert(i+N,group[i][j]); G2.dfs(1,0,0);G2.get_ancestor(); memset(lable,0,sizeof(lable)); while(Q--){ int x=read(),y=read(),lca=G2.LCA(x,y); lable[x]++;lable[y]++;lable[lca]--;lable[fa[lca][0]]--; } G2.re_dfs(1); } void output(){ up(i,1,N)printf("%d\n",lable[i]); } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); output(); return 0; }