poj2117求割点后最多的块。

tarjan算法，枚举割点（注意此题无向图可能不连通），每个割点分割后最大块数+连通分量-1即可。开始老是TLE，后来比较了他人代码，只在vector<vector<int.>.>，用全局变量即可，用局部TLE。记住教训。

#include<iostream>  //600+MS/5000MS

#include<cstdio>

#include<vector>  //用这个做链表，保存边，方便。

#include<cstring>

using namespace std;

int subnet[10001];   //割点i有subnet[i]+1个子网络

int dfn[10001];

int low[10001];

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

int time=0;           //时间戳

int son=0;            //DFS树根的孩子结点个数，割点判断条件之一

vector<vector<int> >v(10001);    //做全局变量时时间降低，若做局部变量，虽然节省空间，用参数传递，时间增加TLE！！！！！！！！！

int min(int a,int b)

{

    if(a<=b)return a;

    return b;

}

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

{

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

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

    for(int i=0;i<daxiao;i++)         //遍历U的所有边

    {

        if(visited[v[u][i]]==0)

        {

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

            tarjan(root,v[u][i],u);

            low[u]=min(low[u],low[v[u][i]]);  //更新1

                                              //回溯时判断

            if(u==root)                          //割点判断条件1

            {

                son++;

            }

            else if(dfn[u]<=low[v[u][i]])       //非DFS树根 割点判断条件2

            {

                subnet[u]++;                //每个U的子孩子对应一个块（u同时属于这些块）

            }

        }

        else if(v[u][i]!=fa)         //不必跟新父节点

        {

            low[u]=min(dfn[v[u][i]],low[u]);   //更新2

        }

   }

}

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m)&&(n||m))

    {

        if(m==0){printf("%d\n",n-1);continue;}

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

       {

           dfn[i]=low[i]=visited[i]=subnet[i]=0;

           v[i].clear();

       }

        int a,b;

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

        {

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

           v[a].push_back(b);

           v[b].push_back(a);

        }

        time=0;son=0;

        int countzitu=0;  int count=0;

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

        if(dfn[i]==0)

         {

             visited[i]=1;

             tarjan(i,i,-1);

             countzitu++;

             if(count<son)count=son;

             son=0;

         }

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

        if(subnet[i]+1>count)

         {count=subnet[i]+1;}

      printf("%d\n",count+countzitu-1);

    }

    return 0;

}

巴特西

poj2117求割点后最多的块。

最新文章

热门文章