tarjan算法,枚举割点(注意此题无向图可能不连通),每个割点分割后最大块数+连通分量-1即可。开始老是TLE,后来比较了他人代码,只在vector<vector<int.>.>,用全局变量即可,用局部TLE。记住教训。
#include<iostream> //600+MS/5000MS #include<cstdio> #include<vector> //用这个做链表,保存边,方便。 #include<cstring> using namespace std; int subnet[10001]; //割点i有subnet[i]+1个子网络 int dfn[10001]; int low[10001]; int visited[10001]; //标记访问 int time=0; //时间戳 int son=0; //DFS树根的孩子结点个数,割点判断条件之一 vector<vector<int> >v(10001); //做全局变量时时间降低,若做局部变量,虽然节省空间,用参数传递,时间增加TLE!!!!!!!!! int min(int a,int b) { if(a<=b)return a; return b; } void tarjan(int root,int u,int fa) //dfs { dfn[u]=low[u]=++time; int daxiao=v[u].size(); for(int i=0;i<daxiao;i++) //遍历U的所有边 { if(visited[v[u][i]]==0) { visited[v[u][i]]=1; tarjan(root,v[u][i],u); low[u]=min(low[u],low[v[u][i]]); //更新1 //回溯时判断 if(u==root) //割点判断条件1 { son++; } else if(dfn[u]<=low[v[u][i]]) //非DFS树根 割点判断条件2 { subnet[u]++; //每个U的子孩子对应一个块(u同时属于这些块) } } else if(v[u][i]!=fa) //不必跟新父节点 { low[u]=min(dfn[v[u][i]],low[u]); //更新2 } } } int main() { int n,m; while(~scanf("%d%d",&n,&m)&&(n||m)) { if(m==0){printf("%d ",n-1);continue;} for(int i=0;i<n;i++) { dfn[i]=low[i]=visited[i]=subnet[i]=0; v[i].clear(); } int a,b; for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } time=0;son=0; int countzitu=0; int count=0; for(int i=0;i<n;i++) if(dfn[i]==0) { visited[i]=1; tarjan(i,i,-1); countzitu++; if(count<son)count=son; son=0; } for(int i=0;i<n;i++) if(subnet[i]+1>count) {count=subnet[i]+1;} printf("%d ",count+countzitu-1); } return 0; }