<题目链接>
题目大意：
给出一个无向图，求出其中的割点数量。
解题分析：
无向图求割点模板题。
一个顶点u是割点，当且仅当满足
(1) u为树根，且u有多于一个子树。
(2) u不为树根，且满足存在(u,v)为树枝边(或称 父子边，即u为v在搜索树中的父亲)，使得 dfn(u)<=low(v)。（也就是说V没办法绕过 u 点到达比 u dfn要小的点）
注：这里所说的树是指，DFS下的搜索树。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M =1e4+;
int dfn[M],low[M],father[M],head[M];
int n,m,tot,top,cnt;
struct EDGE{
int to,next;
}edge[M];
void init(){
memset(head,-,sizeof(head));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(father,,sizeof(father));
tot=cnt=;
}
void add(int u,int v){
edge[++cnt].to=v,edge[cnt].next=head[u];
head[u]=cnt;
}
void Targan(int u,int fa){
dfn[u]=low[u]=++tot;
father[u]=fa; //记录每个节点的父亲
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
Targan(v,u);
low[u]=min(low[u],low[v]);
}
else if(fa!=v){
low[u]=min(dfn[v],low[u]);
}
}
}
void solve(){
int rootson=,ans=;
bool cut[M]={false}; //标记该点是否为割点
Targan(,-); //从1开始遍历整张图
for(int i=;i<=n;i++){
int u=father[i];
if(u==)rootson++; //父亲为根节点，则根节点的分支+1
else if(dfn[u]<=low[i])cut[u]=true; //说明i无法绕过它的父亲节点到达比dfn[u]更小的节点,说明u为割点
}
for(int i=;i<=n;i++){
if(cut[i])ans++;
}
if(rootson>)ans++; //如果根节点的子树数>1,则说明该根节点是割点
printf("%d\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF,n){
init();
int u,v;
char ch;
while(scanf("%d",&u),u){
while(scanf("%d%c",&v,&ch)){
add(u,v),add(v,u);
if(ch=='\n')break;
}
}
solve();
}
}
2018-10-17