题目链接：传送门
思路：
（1）这道题的图可能不连通，所以需要多次Tarjan；
（2）设置cut[i]=x数组表示第i个节点被删除后右多少个子图（这个只是在一个图中），如果是根节点就要-1，因为根节点都满足
num[v]==low[u].
（3）mx的初始值设为最小值（-9999999），因为有可能cur[i]=-1,存在根节点所在的图是双联通图。
参考文章：传送门
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn = 100100; int num[maxn],low[maxn],cut[maxn],tim; vector <int> vc[maxn]; void Init() { memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); for(int i=0;i<maxn;i++) vc[i].clear(); tim=0; } void Tarjan(int u,int pre) { int i,v; num[u]=low[u]=++tim; for(int i=0;i<vc[u].size();i++){ v=vc[u][i]; if(!num[v]){ Tarjan(v,u); low[u]=min(low[u],low[v]); if(num[u]<=low[v]) cut[u]++; } else if(pre!=v) low[u]=min(low[u],num[v]); } } int main(void) { int n,m,i,j,x,y; while(~scanf("%d%d",&n,&m)&&(n+m)){ Init(); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); vc[x].push_back(y); vc[y].push_back(x); } int cnt=0,mx=-99999999; for(i=0;i<n;i++) if(!num[i]){ Tarjan(i,-1); cnt++;cut[i]--; } for(i=0;i<n;i++) mx=max(mx,cut[i]); printf("%d\n",mx+cnt); } return 0; }
原文：https://www.cnblogs.com/2018zxy/p/10360258.html
