一共只会删除一个点,将每个点双连通分量分三种情况讨论
第一种:点双连通分量没有割点,那么为了保证一定可以逃出去,至少需要两个点
第二种:点双连通分量有且只有一个割点,此处割点是绿色的点,那么对于这种点双连通分量
就需要在每个只有一个割点的双连通分量中设置一个逃生点
第三种:点双连通分量有割点并且大于一个,此处对于双连通分量 { 1,2,3 } 中有割点2 1,那么对于这种点双连通分量不需要做任何处理
因为只会塌方一个点,并且由第二种情况,每个只有一个割点的双连通分量都会设置一个逃生点,那么第三种双连通分量某个割点塌方的话
他依旧可以从另外的割点逃出去,一直逃到逃到只有一个割点的双连通分量
#include<bits/stdc++.h> using namespace std; #define endl "\n" #define int long long typedef long long ll; const int N=505; std::vector<int>edge[N],cc[N]; int dfn[N],low[N],cut[N],idx,m,cnt; stack<int>stk; void dfs(int x,int fa,int root){ dfn[x]=low[x]=++idx; stk.push(x); int son=0; //判断孤立点 if(x==root&&(int)edge[x].size()==0){ cut[x]=1; ++cnt; cc[cnt].push_back(x); return; } for(auto y:edge[x]){ if(!dfn[y]){ dfs(y,x,root); son++; low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ cut[x]=1; ++cnt; cc[cnt].push_back(x); while(1){ int top=stk.top(); cc[cnt].push_back(top); stk.pop(); if(top==y)break; } } }else if(y!=fa){ low[x]=min(low[x],dfn[y]); } } if(x==1&&son<=1)cut[x]=0; } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int cs=0; while(1){ ++cs; int m;cin>>m; if(!m)break; int n=0; for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; edge[x].push_back(y); edge[y].push_back(x); n=max({n,x,y}); } for(int i=1;i<=n;i++){ low[i]=dfn[i]=cut[i]=0; } while(!stk.empty())stk.pop(); idx=cnt=0; for(int i=1;i<=n;i++){ if(!dfn[i])dfs(i,i,i); } cout<<"Case "<<cs<<": "; int ans1=0,ans2=1; for(int i=1;i<=cnt;i++){ int ncut=0; for(auto j:cc[i])ncut+=cut[j]; if(ncut==0){ ans1+=2; ans2*=(int)cc[i].size()*((int)cc[i].size()-1)/2; }else if(ncut==1){ ans1+=1; ans2*=(int)cc[i].size()-1; } } cout<<ans1<<' '<<ans2<<endl; for(int i=1;i<=n;i++)edge[i].clear(),cc[i].clear(); } return 0; }View Code
标签:缩点,Tarjan,点双,连通,int,割点,low,分量 From: https://www.cnblogs.com/zhujio/p/17609495.html