来源：
Central Europe 1996
思路：
Tarjan求割点。
一个点$x$为割点当且仅当：
1.$x$为根结点且有两棵不相交的子树。
2.$x$不为根结点且它的子树中没有可以返回到$x$的祖先的边。
实现细节：
当$x$为根结点时，不能单纯地统计它的度，而是应该统计其不相交子树的个数，因为如果刚好是一个环，每个点的度都是$2$，但去掉这个点以后还是连通的。
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 const int V=100; 5 const int root=1; 6 std::vector<int> e[V]; 7 inline void add_edge(const int u,const int v) { 8 ????e[u].push_back(v); 9 }10 int dfn[V],low[V],cnt;11 bool isCut[V];12 void Tarjan(const int x) {13 ????int child=0;14 ????dfn[x]=low[x]=++cnt;15 ????for(unsigned i=0;i<e[x].size();i++) {16 ????????int &y=e[x][i];17 ????????if(!dfn[y]) {18 ????????????Tarjan(y);19 ????????????low[x]=std::min(low[x],low[y]);20 ????????????child++;21 ????????????if(x!=root&&low[y]>=dfn[x]) isCut[x]=true;22 ????????????if(x==root&&child>1) isCut[x]=true;23 ????????}24 ????????else {25 ????????????low[x]=std::min(low[x],dfn[y]);26 ????????}27 ????}28 }29 inline void init() {30 ????for(int i=0;i<V;i++) e[i].clear();31 ????memset(dfn,0,sizeof dfn);32 ????memset(low,0,sizeof low);33 ????memset(isCut,0,sizeof isCut);34 ????cnt=0;35 }36 int main() {37 ????for(;;) {38 ????????int n;39 ????????scanf("%d",&n);40 ????????if(!n) return 0;41 ????????init();42 ????????for(;;) {43 ????????????int u;44 ????????????scanf("%d",&u);45 ????????????if(!u) break;46 ????????????while(getchar()!=‘\n‘) {47 ????????????????int v;48 ????????????????scanf("%d",&v);49 ????????????????add_edge(u,v);50 ????????????????add_edge(v,u);51 ????????????}52 ????????}53 ????????Tarjan(root);54 ????????int ans=0;55 ????????for(int i=1;i<=n;i++) {56 ????????????ans+=isCut[i];57 ????????}58 ????????printf("%d\n",ans);59 ????}60 }[POJ1144]Network
原文地址：http://www.cnblogs.com/skylee03/p/7433796.html