2062175 2006-09-11 23:10:31 Accepted 1119 C++ 00:00.08 4368K St.Crux     若干年以前，这个题就应该被AC了——对弱题的冲动、严蔚敏老师的数据结构、标程——AC的三大要素我都有了，但是我一直停留在第一阶段——被邓公称作是一百年不变的初级阶段。三十年前，光明日报的编辑写过，实践是检验真理的唯一标准。然而在特定的时间，特定的地点，特定的人物身上，实践只会成为怀疑真理的唯一标准。幸好我还有第三样法宝。     修改过的标程 #include <cstdio>#include <string> int x, y, vx, idx, a[1001][1001], dfn[1001], low[1001], sub[1001], root, c = 0, mx, mn;// low[] means the lowest point one root and its subtree point to int min(int a, int b){ return a > b ? b : a;} void init(){ memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(sub, 0, sizeof(sub)); idx = 1, low[vx] = dfn[vx] = idx, root = 0;} void dfs(int i){ int k;  for(k = mn; k <= mx; k ++) {  if(a[i][k])  // k adjacent to i  {   if(!dfn[k]) // k not visited -- k is in subtree   {    idx ++;    dfn[k] = low[k] = idx;    dfs(k);     low[i] = min(low[i], low[k]);    // and if k is subtree, judge if it is AP(articulation point)    if(low[k] >= dfn[i])    {     if(i == vx) root ++;     if(i != vx) sub[i] ++;    }   }   else // k visited -- k is ancestor   {    low[i] = min(low[i], dfn[k]);   }  } }} void print(){ if(c ++) printf("\n"); printf("Network #%d\n", c); int i, f = 0; //pl(); if(root > 1) sub[vx] = root - 1; for(i = mn; i <= mx; i ++) {  if(sub[i])  {   f = 1;   printf("  SPF node %d leaves %d subnets\n", i, sub[i] + 1);  } } if(!f)  printf("  No SPF nodes\n");} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d", &x) && x) {    vx = x;  memset(a, 0, sizeof(a));  scanf("%d", &y);  a[x][y] = 1;  a[y][x] = 1;  mx = x, mn = x;  if(y > mx) mx = y;  if(y < mn) mn = y;  while(scanf("%d", &x) && x)  {   scanf("%d", &y);   a[x][y] = 1;   a[y][x] = 1;   if(x > mx) mx = x;   if(x < mn) mn = x;   if(y > mx) mx = y;   if(y < mn) mn = y;  }  init();  dfs(vx);  print(); } return 0;}    

评论