Tarjan算法求解割点
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int maxn=1111;//有多少个结点 vector<int>G[maxn]; int visited[maxn];//标记该节点有没有访问过 int node;//顶点数目 int tmpdfn;//dfs过程中记录当前的深度优先搜索序数 int dfn[maxn];//记录每个顶点的深度优先搜索序数 int low[maxn];//每个顶点的low值，根据该值来判断是否是关节点 int son;//根结点的有多少个孩子，如果大于等于2，则根结点为关节点 int subnets[maxn];//记录每个结点（去掉该结点后）的连通分量的个数 void init() { for(int i=0;i<maxn;i++) G[i].clear(); low[1]=dfn[1]=1; tmpdfn=1;son=0; memset(visited,0,sizeof(visited)); visited[1]=1; memset(subnets,0,sizeof(subnets)); } void dfs(int u) { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!visited[v]) { visited[v]=1; tmpdfn++; dfn[v]=low[v]=tmpdfn; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { if(u!=1) subnets[u]++; if(u==1) son++; } } else low[u]=min(low[u],dfn[v]); } } int main() { int u,v; int number=1; while(1) { node=0; scanf("%d",&u); if(u==0) break; scanf("%d",&v); if(u>node) node=u; if(v>node) node=v; //初始化 init(); //无向图 G[u].push_back(v); G[v].push_back(u); while(1) { scanf("%d",&u); if(u==0) break; scanf("%d",&v); if(u>node) node=u; if(v>node) node=v; //无向图 G[u].push_back(v); G[v].push_back(u); } if(number>1) printf(" "); printf("Network #%d ",number); number++; dfs(1); if(son>1) subnets[1]=son-1; int Find=0; for(int i=1;i<=node;i++) if(subnets[i]) { Find=1; printf(" SPF node %d leaves %d subnets ",i,subnets[i]+1); } if(!Find) printf(" No SPF nodes "); } return 0; }