Tomcat手工搭建Jsp和Servlet程序
标签：blog class c code tar a
题意：求一个无向图的，去掉两个不同的点后最多有几个连通分量。
思路：枚举每个点，假设去掉该点，然后对图求割点后连通分量数，更新最大的即可。算法相对简单，但是注意几个细节：
1：原图可能不连通。
2：有的连通分量只有一个点，当舍去该点时候，连通分量-1；
复习求割点的好题！
#include
#include
#include
using namespace std;
int n,m;
vector >e(10010);
int dfn[5010];int low[5010];int vis[5010];
int times=0;
int subset[5010];
int root=0;
int rf=0;
int son=0;
void tarjan(int u,int fa) //无向图tarjan记录父亲
{
if(u==rf)return; //是被枚举的点，舍去（从图中删去）。
dfn[u]=low[u]=times++;
for(int i=0;imaxson)maxson=son; //求出每个连通分量的根的最大的son
son=0; //每个连通分量要更新son
}
}
if(e[i].size()==0)scc--; // 注意点！！！：该连通分量只有一个点！舍去的话就没了。
for(int ii=0;iimaxx)maxx=scc+subset[ii]+1-1;
}
if(scc+maxson-1>maxx)maxx=maxson+scc-1;
for(int j=0;j
Tomcat手工搭建Jsp和Servlet程序,搜素材,soscw.com
Tomcat手工搭建Jsp和Servlet程序
标签：blog class c code tar a
原文地址：http://blog.csdn.net/jerry_1126/article/details/26171057
评论