欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

B - Network(tarjan求割点和桥板子)

程序员文章站 2022-06-01 11:55:52
...

https://www.luogu.com.cn/problem/UVA315


板子:

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=200;
typedef long long LL;
vector<LL>g[maxn];
LL fa[maxn],dfn[maxn],low[maxn],times=0;
bool ge[maxn];
void tarjan2(LL x)
{
    dfn[x]=low[x]=++times;
    LL child=0;
    for(LL i=0;i<g[x].size();i++)
    {
        LL to=g[x][i];
        if(!dfn[to])
        {
            child++;fa[to]=x;
            tarjan2(to);
            if(-1==fa[x]&&child>=2) ge[x]=true;
            if(-1!=fa[x]&&low[to]>=dfn[x]) ge[x]=true;
            if(low[to]>dfn[x]){
               ///cout<<x<<"->"<<to<<" is bridge"<<endl;
            }
            low[x]=min(low[x],low[to]);
        }
        else if(to!=fa[x]) low[x]=min(low[x],dfn[to]);
    }
}
int main(void)
{
    for(LL i=1;i<=n;i++) if(!dfn[i]) tarjan2(i);
}

对于算法的理解:

注意点一:第二次更新dfn不空的节点注意要min(low[x],dfn[to]);

https://blog.csdn.net/Kamisama123/article/details/75007415(这个地方的解释)

B - Network(tarjan求割点和桥板子)

考虑这样一幅图:
假如我们用low【v】来更新low【u】,一种存在的遍历顺序会导致这样一种情况。
节点3的dfn为3,low为1,节点5的dfn为5,low为1,节点4的dfn为4,low为1。
这种情况导致3不被判定为割点。


注意点2:判断儿子和父亲的关系是在搜索树中的。所以x为root的时候且有两个儿子只有一种情况。

注意点3:x是割点.cas1:非root点&&有儿子&&low[x的儿子]>=dfn[x];

case2:root点&&有>=2个儿子

x-y是桥:low[y]>dfn[x];

复习参考视频:https://www.bilibili.com/video/BV1GE411G7Kq


关于本题:是割点的板子题。输入比较毒瘤。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=200;
typedef long long LL;
vector<LL>g[maxn];
LL fa[maxn],dfn[maxn],low[maxn],times=0;
bool ge[maxn];
void tarjan2(LL x)
{
    dfn[x]=low[x]=++times;
    LL child=0;
    for(LL i=0;i<g[x].size();i++)
    {
        LL to=g[x][i];
        if(!dfn[to])
        {
            child++;fa[to]=x;
            tarjan2(to);
            if(-1==fa[x]&&child>=2) ge[x]=true;
            if(-1!=fa[x]&&low[to]>=dfn[x]) ge[x]=true;
            if(low[to]>dfn[x]){
               ///cout<<x<<"->"<<to<<" is bridge"<<endl;
            }
            low[x]=min(low[x],low[to]);
        }
        else if(to!=fa[x]) low[x]=min(low[x],dfn[to]);
    }
}
int main(void)
{
  ///cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;
  while(cin>>n&&n)
  {
    memset(fa,-1,sizeof(fa));memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));memset(ge,0,sizeof(ge));
    times=0;
    for(LL i=0;i<=n+10;i++) g[i].clear();
    LL sz;
    while(cin>>sz&&sz)
    {
        while(1)
        {
            char ch=getchar();if(ch=='\n') break;
            LL v;cin>>v;
            g[sz].push_back(v);g[v].push_back(sz);
        }
    }
    LL sum=0;
    for(LL i=1;i<=n;i++) if(!dfn[i]) tarjan2(i);
    for(LL i=1;i<=n;i++) if(ge[i]) sum++;
    cout<<sum<<endl;
  }
  return 0;
}

 

相关标签: tarjan 模板类