uva 10765 Doves and bombs(双联通分量)

?

给一个n个点联通的无向图，要求的是去掉图中的某个点后，所形成的连通块的个数。按形成的连通块的个数的从多到少 和 点的编号从大到小 输出前m个结果。

解题思路：

说到解题方法，就要说一下求双连通分量这个事。

我原来理解双连通分量，以为其形式必然会是 几个点围成一个环才能叫一个双连通分量。其实不然。

定义：在无向连通图中，如果删除该图的任何一个结点都不能改变该图的连通性，则该图为双连通的无向图。

如果有两个点a,b相连，那么a-b就是一个双联通分量。它符合上面的定义。并且在这个图中，其实有两条边，a-b和b-a。

这么看来，也就能理解我在输出一个图中所有的双连通分量时，那些并不构成环的有两个点组成的边也能作为一个双联通分量输出。 也才能理解为什么这道题目可以用求双连通分量的方法这么做

?

解题思路：

如果这个点是割点，这个点必然会出现在多个联通分量中。那么去掉这个点，会形成>=两个连通块。

如果不是割点，那去掉这个点并不会有更多的连通块出现。注意这个时候，应该是1个连通块而不是0个。

?

这样我们首先求出所有的连通分量保存下来(bcc[maxn]),然后遍历所有的双连通分量，对每一个双连通分量其中的每一个点都判断其是否为割点（iscut[x]），如果是，那么其形成的连通块个数就+1(ans[x].num++);

?

code:

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; const int maxn = 10005; //int n,k; struct node{ int id; int num; bool operator<(const node et) const{ if(num != et.num) return num > et.num; else return id < et.id; } }ans[maxn]; int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; ///bccno 是每个节点所属的双连通分量的编号 ///bcc_cnt是双连通分量的个数 vector
        
          G[maxn], bcc[maxn]; ///bcc[]数组记录了每一支双连通分量 struct Edge{ int u, v; }; stack
         
           S; int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i=0; i
          
           = pre[u]){ iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear(); for(;;){ Edge x = S.top(); S.pop(); if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; } if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; } if(x.u == u && x.v == v) break; } } } else if(pre[v] < pre[u] && v != fa){ S.push(e); lowu = min(lowu, pre[v]); } } if(fa < 0 && child == 1) iscut[u] = 0; return lowu; } void find_bcc(int n){ memset(pre, 0, sizeof(pre)); memset(iscut, 0, sizeof(iscut)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = 0; for(int i=0; i
           
            
?