<1>弱连通的有向图如果没有出度或入度为0的节点则它必强连通
 =>弱连通的有向图所有节点的入度等于所有节点的出度。任给两个节点u,v，可以证明必有u到v的路。
<2>有向图入度,出度为0的节点数分别为Iz,Oz.则通过给它加边，使它变成强连通图，最少要加max{Iz,Oz}条边。
 =>考虑将Oz个出度为0的节点与Iz个入度为0的节点相连接，若Oz!=Iz则将多出来的再接到其它节点上，以消除出度或入度为0的节点。即最少需加max{Iz, Oz}条边才能变成没有出度或入度为0的节点的有向图。
   对于有多个弱连通分量的有向图,比如图G有Gx, Gy两个弱连通分量，其入度,出度为0的节点数分别为Ix,Ox和Iy,Oy. 不妨设Ox>=Iy,则考虑将Gx的Ox个出度为0的节点中的Iy个连到Gy的Iy个入度为0的节点上。这样就成了一个弱连通的有向图，它的入度,出度为0的节点数分别为Ix,Ox-Iy+Oy.则它的最少加边数为Iy+max{Ix,Ox-Iy+Oy},即为max{Ix+Iy,Ox+Oy}

• Re:(⊙_⊙)！my idea~ (372) gbastc 2011-08-04 22:04:30