一、定义：
在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。
如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点。
二、模板
- 邻接矩阵实现（时间复杂度太高，没什么用）
#include<cstdio> #include<cstring> using namespace std; int n,m,root,w[sizen][sizen]; int num[sizen]={0},low[sizen]={0},flag[sizen]={0},t=0; void dfs(int cur, int father); int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) w[i][j]=0; for(int i=1;i<=m;i++) { cin>>a>>b; w[a][b]=1; w[b][a]=1; } root=1; dfs(1,root); } void dfs(int cur,int father) { int child=0; t++; num[cur]=t; low[cur]=t; for(int i=1;i<=n;i++) { if(w[cur][i]==1) { if(num[i]==0) { child++; dfs(i,cur); low[cur]=min(low[cur],low[i]); if(cur!=root && low[i]>=num[cur]) flag[cur]=1; if(cur==root && child==2) flag[cur]==1; } else if(i != father) { low[cur]=min(low[cur],num[i]); } } } }
- 邻接表实现
#include<cstdio> #include<cstring> #include<iostream> #define sizen 5000 #define sizem 500050 using namespace std; int n,m,root,next[2*sizem],first[sizen],u[2*sizem],v[2*sizem]; int num[sizen]={0},low[sizen]={0},flag[sizen]={0},t=0; void dfs(int cur, int father); int main() { cin>>n>>m; memset(next,-1,sizeof(next)); memset(first,-1,sizeof(first)); for(int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); u[m+i]=v[i]; v[m+i]=u[i]; next[i]=first[u[i]]; first[u[i]]=i; next[m+i]=first[u[m+i]]; first[u[m+i]]=m+i; } m*=2; root=1; dfs(1,root); for(int i=1;i<=n;i++) if(flag[i])cout<<i<<endl; } void dfs(int cur,int father) { int child=0; t++; num[cur]=t; low[cur]=t; int i=first[cur]; while(i!=-1) { if(num[v[i]]==0) { child++; dfs(v[i],cur); low[cur]=min(low[cur],low[v[i]]); if(cur!=root && low[v[i]]>=num[cur]) flag[cur]=1; if(cur==root && child==2) flag[cur]=1; } else if(v[i]!=father) { low[cur]=min(low[cur],num[v[i]]); } i=next[i]; } }
- tarjan图不一定联通的情况：
for(int i=1;i<=n;i++) { if(num[i]==0) root=i,dfs(root,root); }
每个点搜一遍
- 割边：修改 >= 为 >（原因自己想）
if(cur!=root && low[v[i]]>num[cur]) flag[cur]=1;
- +一点点强连通分量
Luogu P3469 [POI2008]BLO-Blockade
每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。对于每个被决定的城镇，如果它被封锁，有多少访问不会发生，输出结果。挂一个WA代码，待AC:(使用的并查集解决每个版块个数的问题，但是好像用DFS更简单）#include<cstdio> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #define sizen 100050 #define sizem 500050 using namespace std; int n,m,root,next[2*sizem],first[sizen],u[2*sizem],v[2*sizem]; int num[sizen]={0},low[sizen]={0},flag[sizen]={0},t=0; int forefather[sizen],ccount[sizen]; void merge(int x,int y); void dfs(int cur, int father); long long int ltk(int k); int main() { //freopen("testdata.in","r",stdin); //freopen("point.out","w",stdout); cin>>n>>m; memset(next,-1,sizeof(next)); memset(first,-1,sizeof(first)); for(int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); u[m+i]=v[i]; v[m+i]=u[i]; next[i]=first[u[i]]; first[u[i]]=i; next[m+i]=first[u[m+i]]; first[u[m+i]]=m+i; } m*=2; root=1;dfs(root,root); int count=0; for(int i=1;i<=n;i++) if(!flag[i])cout<<2*(n-1)<<endl; else { cout<<ltk(i)+2*(n-1)<<endl; } //if(flag[i])count++; //cout<<count<<endl; //for(int i=1;i<=n;i++) //if(flag[i])cout<<flag[i]<<' '; } void dfs(int cur,int father) { int child=0; t++; num[cur]=t; low[cur]=t; int i=first[cur]; while(i!=-1) { if(num[v[i]]==0) { child++; dfs(v[i],cur); low[cur]=min(low[cur],low[v[i]]); if(cur!=root && low[v[i]]>=num[cur]) flag[cur]=1; if(cur==root && child==2) flag[cur]=1; } else if(v[i]!=father) { low[cur]=min(low[cur],num[v[i]]); } i=next[i]; } } long long int ltk(int k) { for(int i=1;i<=n;i++)forefather[i]=i; for(int i=1;i<=n;i++) { if(i==k)continue; int r=first[i]; if(v[r]==k)r=next[r]; while(r!=-1) { merge(v[r],i); r=next[r]; if(v[r]==k)r=next[r]; } } forefather[k]=0; sort(forefather+1,forefather+n+1); int top=1; ccount[top]=1; for(int i=3;i<=n;i++) { if(forefather[i-1]!=forefather[i]) ccount[++top]=1; else ccount[top]++; } long long int ans=0; for(int i=1;i<=top;i++) for(int j=i+1;j<=top;j++) ans+=ccount[i]*ccount[j]; ans*=2; return ans; } void merge(int x,int y) { int tx=x,ty=y; while(forefather[x]!=x) x=forefather[x]; while(forefather[y]!=y) y=forefather[y]; forefather[x]=y; while(forefather[tx]!=tx) { int j=forefather[tx]; forefather[tx]=y; tx=j; } while(forefather[ty]!=ty) { int j=forefather[ty]; forefather[ty]=y; ty=j; } }
- 待解决题单：POJ1144 POJ1523 HDU4738 POJ3694