题解：
求割点模板题
注意输入格式转换
需要考虑重边
代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include<vector> #include <map> using namespace std; const int maxn = 5010;//点数 const int maxm = 20010;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; bool cut;//是否是桥标记 } edge[maxm]; int head[maxn],tot; int low[maxn],dfn[maxn],Stack[maxn],belong[maxn];//belong数组的值是1~scc int Index,top; int scc;//边双连通块数/强连通分量的个数 bool Instack[maxn]; int bridge;//桥的数目 bool cut[maxn]; void addedge(int u,int v) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut=false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; low[u] = dfn[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son=0; for(int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !dfn[v] ) { son++; Tarjan(v,u); if( low[u] > low[v] )low[u] = low[v]; if(low[v] > dfn[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } if(u == pre && son > 1)cut[u] = true; if(u != pre && low[v] >= dfn[u])cut[u] = true; } else if( Instack[v] && low[u] > dfn[v] ) low[u] = dfn[v]; } if(low[u] == dfn[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; belong[v] = scc; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } void solve(int n) { memset(dfn,0,sizeof(dfn)); memset(Instack,false,sizeof(Instack)); memset(cut,0,sizeof cut); Index = top = scc = 0; bridge = 0; for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i,i); int ans = 0; for(int i = 1;i <= n;i++) if(cut[i]) ans++; printf("%d\n",ans); } int g[105][105]; int main() { int n; int a,b; while(~scanf("%d",&n) && n) { init(); memset(g,0,sizeof g); while(~scanf("%d",&a) && a) { while(getchar()!='\n') { scanf("%d",&b); g[a][b]=g[b][a]=1; } } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(g[i][j]) { addedge(i,j); addedge(j,i); } } } solve(n); } return 0; } /* 5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0 */
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; const int maxn = 10010; const int maxm = 100100; struct Edge { int to,next; bool cut;//是否为桥的标记 }edge[maxm]; int head[maxn],tot; int low[maxn],dfn[maxn],Stack[maxn]; int Index,top; bool Instack[maxn]; bool cut[maxn]; int add_block[maxn];//删除一个点后增加的连通块 int bridge; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; low[u] = dfn[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !dfn[v] ) { son++; Tarjan(v,u); if(low[u] > low[v])low[u] = low[v]; //桥 //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<low(v)。 if(low[v] > dfn[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } //割点 //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=low(v) if(u != pre && low[v] >= dfn[u])//不是树根 { cut[u] = true; add_block[u]++; } } else if( low[u] > dfn[v]) low[u] = dfn[v]; } //树根，分支数大于1 if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } void solve(int n) { memset(dfn,0,sizeof(dfn)); memset(Instack,false,sizeof(Instack)); memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i,i); int ans = 0; for(int i = 1;i <= n;i++) if(cut[i]) ans++; printf("%d\n",ans); } void init() { tot = 0; memset(head,-1,sizeof(head)); } int g[105][105]; int main() { int n; int a,b; while(~scanf("%d",&n) && n) { init(); memset(g,0,sizeof g); while(~scanf("%d",&a) && a) { while(getchar()!='\n') { scanf("%d",&b); g[a][b]=g[b][a]=1; } } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(g[i][j]) { addedge(i,j); addedge(j,i); } } } solve(n); } return 0; } /* 5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0 */