只考虑破坏图，进行染色。
白色表示在原图中与1相连，否则为黑色

初始化：
将破坏图中未与1连接的点还有1染成白色，其他点为无色，同时记录此时白色点数量为total。

外层循环遍历，对未染色的点，DFS进行染色。

for(int i = 0; i < n; i++)
  if(!color[i])
    DFS(i)

DFS函数.
void DFS(int k){
  visit[k] = 1;
  int cnt = 0;
  for(i = 1~size)//邻接点{
    if(!visit[i]) DFS(i);
    if(color[i] == WHITE) cnt++;
  }
  if(cnt == total)
    color[k] = BLACK;
  else{
    color[k] = WHITE;
    total++;
  }
}

最后节点数为total - 1(减去第一个点)

• 这个算法错的吧 (173) B06350214 2008-10-01 16:18:01