若干年以前，这个题就应该被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;
}

评论