HDU4738 tarjan割边|割边、割点模板

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4738

坑点：

处理重边
图可能不连通，要输出0
若求出的结果是0，则要输出1，因为最少要派一个人

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int inf = 0x3f3f3f3f;

 struct edge{

     int to,cost;

 };

 vector<edge> g[maxn];

 int num[maxn],low[maxn],index;

 int res;

 int mp[maxn][maxn];//处理两点之间边的条数

 //tarjan

 void tarjan(int cur,int father){

     index++;

     num[cur] = index;

     low[cur] = index;

     for(int i = ;i<g[cur].size();i++){

         if(num[g[cur][i].to] == ){

             tarjan(g[cur][i].to,cur);

             low[cur] = min(low[g[cur][i].to],low[cur]);

             if(low[g[cur][i].to] > num[cur] && mp[cur][g[cur][i].to] == )

                 res = min(res,g[cur][i].cost);

         }else if(g[cur][i].to != father){

             low[cur] = min(low[cur],num[g[cur][i].to]);

         }

     }

 }

 //并查集判断连通性

 int f[maxn];

 int getf(int x){

     if(f[x] == x){

         return x;

     }else{

         return f[x] = getf(f[x]);

     }

 }

 int merge(int l,int r){

     int a = getf(l);

     int b = getf(r);

     if(a != b){

         f[a] = b;

     }

 }

 // 初始化

 void init(int n){

     index = ;

     res = inf;

     memset(num,,sizeof(num));

     memset(low,,sizeof(low));

     memset(mp,,sizeof(mp));

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

         g[i].clear();

         f[i] = i;

     }

 }

 int main(){

     int n,m;

     while(scanf("%d%d",&n,&m) && n && m){

         init(n);

         int a,b,c;

         while(m--){

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

             g[a].push_back(edge{b,c});

             g[b].push_back(edge{a,c});

             merge(a,b);

             mp[a][b]++;

             mp[b][a]++;

         }

         int flag = ;

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

             if(getf(i) != getf()){

                 flag = ;

                 break;

             }

         if(flag){

             puts("");

             continue;

         }

         tarjan(,);

         if(res == )

             res++;

         if(res == inf)

             puts("-1");

         else

             printf("%d\n",res);

     }

     return ;

 }

割边模板：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int inf = 0x3f3f3f3f;

 struct edge{

     int to,cost;

 };

 vector<edge> g[maxn];

 int num[maxn],low[maxn],index;

 //tarjan

 void tarjan(int cur,int father){

     index++;

     num[cur] = index;

     low[cur] = index;

     for(int i = ;i<g[cur].size();i++){

         if(num[g[cur][i].to] == ){

             tarjan(g[cur][i].to,cur);

             low[cur] = min(low[g[cur][i].to],low[cur]);

             if(low[g[cur][i].to] > num[cur])

                 //u-v为割边

         }else if(g[cur][i].to != father){

             low[cur] = min(low[cur],num[g[cur][i].to]);

         }

     }

 }

 // 初始化

 void init(int n){

     memset(num,,sizeof(num));

     memset(low,,sizeof(low));

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

         g[i].clear();

     }

 }

割点模板：

 const int maxn = ;

 const int inf = 0x3f3f3f3f;

 struct edge{

     int to,cost;

 };

 vector<edge> g[maxn];

 int num[maxn],low[maxn],index;

 //tarjan

 void tarjan(int cur,int father){

     int child = ;

     index++;

     num[cur] = index;

     low[cur] = index;

     for(int i = ;i<g[cur].size();i++){

         if(num[g[cur][i].to] == ){

             child++;

             tarjan(g[cur][i].to,cur);

             low[cur] = min(low[g[cur][i].to],low[cur]);

             if(low[g[cur][i].to] >= num[cur] && cur!=root)

                 //cur为割点

             if(cur==root && child>=)

                 //cur为割点

         }else if(g[cur][i].to != father){

             low[cur] = min(low[cur],num[g[cur][i].to]);

         }

     }

 }

 // 初始化

 void init(int n){

     memset(num,,sizeof(num));

     memset(low,,sizeof(low));

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

         g[i].clear();

     }

 }

巴特西

HDU4738 tarjan割边|割边、割点模板

最新文章

热门文章