POJ3177,/3352.求最少添加多少边使无向图边双连通

俩个题一样。tarjan算法应用，开始求桥，WA，同一个边双连通分量中low值未必都相同，不能用此来缩点。后来用并查集来判断，若不是桥，则在一个双连通分量中，并之，后边再查,将同一个双连通分量中的点通过并查集收缩为一个并查集的“祖宗点”，间接完成缩点！

缩点成树后，(leaves+1)/2就不用说了。。。。

#include<iostream> //0MS

#include<vector>

#include<cstring>

#include<cstdio>

using namespace std;

/*struct gebian     //开始时记录割边，然后用同一个连通分量中LOW值相等来判断，错误。

{

    int u,v;

};*/

vector<vector<int> >edge(5001);     //相当于链表，这个真心不错。

//vector<gebian>geb;

int dfn[5001];

int low[5001];

int visited[5001];    //标记访问

int time=0;           //时间戳

int degree[5001];

int father[5001];

int hash[5001][5001];

int min(int a,int b)

{

    if(a<=b)return a;

    return b;

}

int find(int x){return x==father[x]?x:find(father[x]);}

void tarjan(int u,int fa)  //dfs

{

    dfn[u]=low[u]=++time;

    int daxiao=edge[u].size();

    for(int i=0;i<daxiao;i++)

    {

        int child=edge[u][i];

        if(visited[child]==0)

        {

            visited[edge[u][i]]=1;

            tarjan(edge[u][i],u);

            low[u]=min(low[u],low[edge[u][i]]);

            if(dfn[u]<low[edge[u][i]])        //是桥

            {

              /*  gebian temp;

                temp.u=u;

                temp.v=edge[u][i];

               geb.push_back(temp);*/

               ;

            }

            else                        //不是桥，必在同一边连通分量中

            {

                father[child]= u;    //并之

            }

        }

        else if(edge[u][i]!=fa)

        {

            low[u]=min(dfn[edge[u][i]],low[u]);

        }

   }

}

int solve(int n)

{

    int leaves=0;

    //int daxiao1=geb.size();

   // cout<<daxiao1<<endl;

  /*  for(int i=0;i<daxiao1;i++)

    {

     //   cout<<low[geb[i].v]<<endl;

       // cout<<low[geb[i].u]<<endl;

        degree[low[geb[i].v]]++;

        degree[low[geb[i].u]]++;

    }

    for(int i=1;i<=n;i++)

    {

        cout<<low[i]<<" ";

         degree[low[i]]++;

    }*/

    for(int i=1;i<=n;i++)  //枚举边

    {

        int len=edge[i].size();

        for(int j=0;j<len;j++)

        {

            if( hash[i][edge[i][j]]||hash[edge[i][j]][i])continue; //hash判重

            int xx=find(i);int yy=find(edge[i][j]);

            hash[i][edge[i][j]]=1;hash[edge[i][j]][i]=1;

            if(xx!=yy)

            {

                degree[xx]++;

                degree[yy]++;

            }

        }

    }

     for(int i=1;i<=n;i++)

    {

        if(degree[i]==1)  //叶子

        {

            leaves++;

        }

    }

    return (leaves+1)/2;

}

int main()

{

    int n,m;

      scanf("%d%d",&n,&m);

        int a,b;

     for(int i=0;i<=n;i++)

        father[i]=i;

        for(int i=0;i<m;i++)

        {

           scanf("%d%d",&a,&b);

           edge[a].push_back(b);

           edge[b].push_back(a);

        }

        visited[1]=1;

        tarjan(1,-1);

        cout<<solve(n)<<endl;

       return 0;

}

巴特西

POJ3177,/3352.求最少添加多少边使无向图边双连通

最新文章

热门文章