首页 > 代码库 > poj Transferring Sylla(如何快速的判断一个图是否是3—连通图,求割点,割边)

poj Transferring Sylla(如何快速的判断一个图是否是3—连通图,求割点,割边)

                                  Transferring Sylla

 

首先,什么是k连通图?k连通图就是指至少去掉k个点使之不连通的图。

题目:

   题目描述的很裸,就是给你一张图要求你判断这图是否是3-连通图。

 

算法分析:

   

 /////////////////////////////////////////////////////////////////////  

              (网上别人的分析,分析的很好所以直接引用了) 

 考虑一下不可行的情况,就是存在两点间的路径条数<3情况,那么我们可以去枚举两个点a和b,然后将其和相邻的边删除,然后判断联通块个数,如果块数大于1则存在路径条数<3的情况,否则不存在,因为如果a和b是一个路径条数<3的点对的路径上的点,如果将其破坏了,这两个点必然不会再联通,因为不可行的情况路径条数最多为2,因此只需要枚举两个点。

/////////////////////////////////////////////////////////////////////////

  但是这肯定超时!

   所以,我们还要优化。我们可以想到既然枚举两个点会超时,那么现在我只枚举一个点呢?当然是可以的。

但是,为什么可以只枚举一个点呢?因为,我们从割点的定义可以知道当一个图是强连通图时候,那么他一定没有割点。所以,当我们枚举到了删除点的时候,那么在剩下的图中如果存在割点那个这个图一定不是3-连通图。因为,此时我们只要删除两条边就可以使其不连通了。

 

给出求解割点割边的模板,这题只要一套模板就可以了。

/////////////    DATA    /////////////////////
vector<int> G[MAXN];
int V,E;
bool cut[MAXN]; // 是否是割点
int color[MAXN]; //0:没有访问 1:正在访问 2:已经访问
int lowc[MAXN];  //表示i及i的子孙相连的辈分最高的祖先节点所在的深度
int d[MAXN];  //表示i节点在树中的深度
int root;  //根节点
int fath; //父节点
int pcnt; //割点个数
int egcnt; //割边个数
bool flag; //是否存在割点

/////////////  DATE END  ////////////////////////


//初始化
void init(){
    flag = false;
    for(int i = 0;i <= V;++i)
        G[i].clear();
}


/////////////////  Tarjan  //////////////////////

void dfs(int u,int fa,int deep){
    color[u] = 1;  //正在访问
    lowc[u] = d[u] = deep; // 深度
    int tot = 0; //子树个数
    int i,v;
    for(i = 0;i < (int)G[u].size();++i){
        v = G[u][i];
        if(v != fa&&color[v] == 1){
            lowc[u] = min(lowc[u],d[v]);
        }
        if(0 == color[v]){
            dfs(v,u,deep + 1);
            tot++; //子树 +1
            lowc[u] = min(lowc[u],lowc[v]);
            //求割点
            if((u == root&&tot > 1)||(u != root&&lowc[v] >= d[u])){
                cut[u] = 1;      //不能将pcnt++写到这里
                flag = true;
            }

            /*

            //求割边 u - > v是割边
            if(lowc[v] > d[u]){
                edge[u][v] = true;
            }

            */
        }
    }
    color[u] = 2;
}

//////////// END  Tarjan ///////////////

void calc(int del){
    pcnt = egcnt = 0;
    memset(cut,0,sizeof(cut));
    memset(color,0,sizeof(color));
    memset(lowc,0,sizeof(lowc));
    memset(d,0,sizeof(d));

    color[del] = 2;
    root = 0;
    if(del == 0)
        root = 1;
    dfs(root,-1,1);

    /*

    //统计割点个数
    for(int i = 0;i < V;++i)
       if(cut[i]) pcnt++;

    */
}
//求图是否是三连通
void solve(){
    
    for(int i = 0;i < V;++i){
        calc(i);
        
        //判断图是否连通
        for(int j = 0;j < V;++j){
            if(0 == color[j]){
                flag = true;
                break;
            }
        }

        if(flag) break;
    }
}


 

 

 

 

 

poj Transferring Sylla(如何快速的判断一个图是否是3—连通图,求割点,割边)