这是一题找无向图的割点的模板题,割点的概念什么的就不再赘述了。这里讲一下这个模板的一个注意点。
dfs中有一个child,它不等于G[u].size()!理由如下:
如上图,1的size是2,但是它的child是1,因为对他进行dfs时,顺序是1-2-3…然后再等到它访问它的第二个节点3时,3已经被访问过了,不能算他的child了,这是一个误区。
代码如下:
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std; const int N = +; stack<int> S;
int scc_cnt;
int dfs_clock;
int dfn[N];
int low[N];
int iscut[N];
vector<int> G[N]; void dfs(int u,int fa)
{
dfn[u]=low[u]=++dfs_clock;
int child = ;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(!dfn[v])
{
child++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) iscut[u]=;
}
else if(dfn[v]<dfn[u] && v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
}
if(fa == - && child == ) iscut[u]=;
} int main()
{
int n;
while(scanf("%d",&n)== && n)
{
memset(dfn,,sizeof(dfn));
memset(iscut,,sizeof(iscut));
dfs_clock=;
for(int i=;i<=n;i++) G[i].clear(); int x;
while(scanf("%d",&x)== && x)
{
while(getchar() != '\n')
{
int y;
scanf("%d",&y);
G[x].push_back(y);
G[y].push_back(x);
}
} dfs(,-);
int cnt=;
for(int i = ;i<=n;i++) if(iscut[i]) cnt++;
printf("%d\n",cnt);
}
return ;
}