割点和桥学习 | FFY's Blog

---

说实话,tarjan是个好东西
然而我却丢了他的脸
到现在我还是很迷糊

• 注意缩点,割点和割边的不同
• 这东西有毒,剧毒mmp
• 割点
• 割边
  • 当存在重边时应将记录父亲节点改为记录父亲边
• 点双联通分量
• 边双联通分量
  • 可在求割边时同时求出
• tarjan

//割边 && 没有重边
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e3+10;
int n,m,head[maxn],num;
int dfn[maxn],low[maxn],input;
bool use[maxn];
struct fy{int to,next;}q[maxn<<2];
void add(int a,int b){q[++num]=(fy){b,head[a]};head[a]=num;}
void tar(int a,int fa)
{
    dfn[a]=low[a]=++input;
    for(int i=head[a];i;i=q[i].next)
    {
        int b=q[i].to;
        if(!dfn[b])
        {
            tar(b,a);low[a]=min(low[a],low[b]);
            if(dfn[a]<low[b])use[i]=true;//感觉这个地方这辈子都不会懂了,太迷幻
            //当然可以和割点一起求
            /*if((child>1&&root==a)||(root!=a&&dfn[a]<=low[b])cutd[i]=true;*/
            //root为根节点
        }
        else if(b!=fa)low[a]=min(low[a],dfn[b]);
        //为什么是b!=fa呢,不懂
    }
}
int main()
{
    scanf("%d%d",&n,&m);int a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tar(i,0);
    for(int i=1;i<=num;i++)if(use[i])printf("%d ",i);
    return 0;
}

当有重边时记录父亲边

//割边&&边双缩点&&有重边&&非边双转边双
#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e3+10;
int n,m,head[maxn],num,bi,cnt,ans,fa[maxn],in[maxn];
bool use[maxn<<2];
int dfn[maxn],low[maxn],input,xx[maxn],w,pa[maxn];
struct fy{int from,to,next,h;}q[maxn<<2];
//h用来装边
void add(int a,int b)
{
    q[++num]=(fy){a,b,head[a],++bi};head[a]=num;
    q[++num]=(fy){b,a,head[b],bi};head[b]=num;
}
void tar(int a)
{
    dfn[a]=low[a]=++input;xx[++w]=a;
    for(int i=head[a];i;i=q[i].next)
    {
        int b=q[i].to;
        if(q[i].h==pa[a])continue;//如果该边走过了就不能再走
        if(!dfn[b])
        {
            pa[b]=q[i].h;//记录父亲边
            tar(b);low[a]=min(low[a],low[b]);
        }
        else low[a]=min(low[a],dfn[b]);
    }
    if(dfn[a]==low[a])//同时边双缩点
    {
        cnt++;
        while(xx[w+1]!=a)
        {fa[xx[w]]=cnt;w--;}
    }
}
int main()
{
    scanf("%d%d",&n,&m);int a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    tar(1);
    for(int i=1;i<=num;i++)
    {
        a=fa[q[i].from];
        b=fa[q[i].to];
        if(a!=b)in[b]++;
    }
    for(int i=1;i<=cnt;i++)if(in[i]==1)ans++;
    printf("%d\n",(ans+1)/2);
    return 0;
}