题目链接:/problem?id=1523
题目大意：连通图，找图中割点，并计算切除该割点后，图中的连通分量个数。
解题思路：
POJ的数据很弱。
Tarjan法求割点。
pre数组，记录这个点的dfs时间位置。
割点的条件是lowv>=pre[u], 即子点比父点先dfs，这时候父点就没有意义了，切掉父点连通分量数肯定会增加。
同时注意特判只有两个点的情况，这时候是不可能出现割点的。
求切除割点后的联通分量数：
从割点出发，把图dfs一遍，如果u=割点，那么对于每个子点v，block++
原理就是，切掉割点后，所有与其连接子点都要受到影响，统计第一次访问的子点v的block即可。
#include "cstdio"#include "vector"#include "string"#include "iostream"#include "cstring"using namespace std;#define maxn 1005struct Edge{int next,to;}e[maxn*2];int pre[maxn],dfs_clock,block,head[maxn],tol;bool cut[maxn],vis[maxn];void addedge(int u,int v){e[tol].to=v;e[tol].next=head[u];head[u]=tol++;}int dfs(int u,int fa){int lowu=pre[u]=++dfs_clock;int child=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(!pre[v]){child++;int lowv=dfs(v,u);lowu=min(lowu,lowv);if(lowv>=pre[u]) cut[u]=true;}else if(pre[v]<pre[u]&&v!=fa) lowu=min(lowu,pre[v]);}if(fa<0&&child==1) cut[u]=false;return lowu;}void check(int u,int fa){vis[u]=true;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(!vis[v]){if(u==fa) block++;check(v,fa);}}}int main(){//freopen("in.txt","r",stdin);int u,v,num=0,no=0;bool flag=false;memset(head,-1,sizeof(head));while(scanf("%d",&u)!=EOF){if(!u){if(!tol) break;printf("Network #%d\n",++no);for(int i=1;i<=num;i++) if(!pre[i]) dfs(i,-1);bool flag=false;for(int i=1; i<=num; i++)if(cut[i]){flag=true;check(i,i);printf(" SPF node %d leaves %d subnets\n",i,block);memset(vis,0,sizeof(vis));block=0;}if(!flag) cout<<" No SPF nodes"<<endl;memset(pre,0,sizeof(pre));memset(cut,false,sizeof(cut));memset(head,-1,sizeof(head));dfs_clock=0;num=0;tol=0;printf("\n");}else{scanf("%d",&v);num=max(num,max(u,v));addedge(u,v);addedge(v,u);}}}
