poj 1144 Network
题意：输入n(n < 100)个点,不一定是连通图，问有多少个割点？
割点:删除某个点之后，图的联通分量增加。
思路:dfs利用时间戳dfs_clock的特性，点u的low函数low[u]代表以u为根的子树所得连到的最"上面"的祖先的时间戳。
即当点u存在一个子节点v，而low[v] >= pre[u]时，u就为割点；u-v即为桥，且割点要在最后判断，不能直接在iscut[] = true;处自增。因为cc_cnt代表的是当前的节点，而该节点可能有多个子节点，这样会导致重复计算。
直接使用了stringstream来读取一行，用了125ms才A.
#include<iostream> #include<sstream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) const int MAXN = 5100; int head[MAXN<<1],tot; struct edge{ int to,w,Next; }e[MAXN<<1]; void ins(int a,int b,int w = 0) { e[++tot].Next = head[a]; e[tot].to = b; e[tot].w = w; head[a] = tot; } int low[MAXN],pre[MAXN],dfs_clock,cc_cnt; bool iscut[MAXN]; int dfs(int u,int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int id = head[u];id;id = e[id].Next){ int v = e[id].to; if(!pre[v]){ child++; int lowv = dfs(v,u); lowu = min(lowu,lowv);//以子节点的low来更新u的low函数； if(lowv >= pre[u]) //表示u-v为桥 iscut[u] = true; } else if(v != fa && pre[v] < pre[u]) lowu = min(lowu,pre[v]); } if(fa < 0 && child == 1) iscut[u] = 0; if(iscut[u]) cc_cnt++; low[u] = lowu; return lowu; } int main() { int n; stringstream ss; while(scanf("%d",&n) == 1 && n){ int u,v; tot = 0;MS0(head); while(scanf("%d",&u) == 1 && u){ string str; getline(cin,str); ss.clear(); ss << str; while(ss >> v){ ins(u,v); ins(v,u); } } cc_cnt = 0;dfs_clock = 0;//设置好时间戳和初始化 MS0(iscut);MS0(pre); rep1(i,1,n)if(pre[i] == 0) dfs(i,-1); printf("%d ",cc_cnt); } return 0; }