Tarjan算法学习笔记

前排提示：先学习拓扑排序，再学习Tarjan有奇效。

--------------------------

Tarjan算法一般用于有向图里强连通分量的缩点。

强连通分量：有向图里能够互相到达的点的集合。（大概是这么个意思，自己意会）

因为能够互相到达，所以宏观上我们可以把它们看成一个点，边权也相应的加起来即可。

下面是Tarjan过程的代码解释：

我们开两个数组，分别为dfn[]和low[]。dfn表示此点的时间戳，low表示最早的时间戳。（即进入某一个环最早的时间戳）

遇到一个没有记录过的点，就把它扔到栈里，不停dfs，直到dfn[]==low[]，即某一个环已经遍历完了，我们就弹栈，将这一个环合并。

代码如下：

void tarjan(int now)

{

    dfn[now]=low[now]=++cnt;

    st[++top]=now;

    vis[now]=;

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (!dfn[to]) tarjan(to),low[now]=min(low[now],low[to]);

        else if (vis[to]) low[now]=min(low[now],dfn[to]);

    }

    if (dfn[now]==low[now])

    {

        tot++;

        while(st[top+]!=now)

        {

            pos[st[top]]=tot;

            sum[tot]+=val[st[top]];

            vis[st[top--]]=;

        }

    }

}

配合拓扑排序，一张新的有向无环图就构造了出来。

-------------------------------------------------------------------------------------

【模板】缩点

给定一个含有n个点m条边的有向图每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

第一行两个整数，为$n$,$m$。

第二行到第$m+1$行有每行有3个整数，分别为$u,v,d$,表示$u\rightarrow v$有一条长度为$d$的边。

输出格式：一行结果。

-------------------------------------------------

Tarjan模板题，只不过加了一点小DP，记忆化搜索即可。注意的地方就是拓扑排序后的重新建图。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int cnt,dfn[maxn],vis[maxn],low[maxn];

int f[maxn],sum[maxn],ans;

int jishu,head[];

int top,st[maxn],pos[maxn],tot;

int n,m,x[maxn],y[maxn],val[maxn];

struct node

{

    int next,to;

}edge[];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void add(int from,int to)

{

    edge[++jishu].next=head[from];

    edge[jishu].to=to;

    head[from]=jishu;

}

void tarjan(int now)

{

    dfn[now]=low[now]=++cnt;

    st[++top]=now;

    vis[now]=;

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (!dfn[to]) tarjan(to),low[now]=min(low[now],low[to]);

        else if (vis[to]) low[now]=min(low[now],dfn[to]);

    }

    if (dfn[now]==low[now])

    {

        tot++;

        while(st[top+]!=now)

        {

            pos[st[top]]=tot;

            sum[tot]+=val[st[top]];

            vis[st[top--]]=;

        }

    }

}

void search(int x)

{

    if (f[x]) return;

    f[x]=sum[x];

    int maxx=;

    for (int i=head[x];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (!f[to]) search(to);

        maxx=max(maxx,f[to]);

    }

    f[x]+=maxx;

}

void clear()

{

    jishu=;

    memset(edge,,sizeof(edge));

    memset(head,,sizeof(head));

}

int main()

{

    n=read(),m=read();

    for (int i=;i<=n;i++) val[i]=read();

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

    {

        x[i]=read(),y[i]=read();

        add(x[i],y[i]);

    }

    for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i);

    clear();

    for (int i=;i<=m;i++) if (pos[x[i]]!=pos[y[i]]) add(pos[x[i]],pos[y[i]]);

    for (int i=;i<=n;i++) search(i),ans=max(ans,f[i]);

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

    return ;

}

另，如果是无向图缩点，一定要加上这句话：

if (edge[i].to==fa) continue;

【模板】割点

给定一个含有n个点m条边的无向图，求图的割点。

------------------------------------------

割点是指去掉这个点整个图便不连通的点。

我们可以同样用Tarjan算法，建立一颗搜索树。

如果此点为根节点，则判断是否有>=2棵子树。如果存在，那么此点为割点。

对于非根节点，如果low[v]>=dfn[u]($u\rightarrow v$)那么u点为割点（因为从u点开始无论怎么走都不可能回到原来的点了）。

思路还是比较清晰的，直接放代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int head[],jishu;

int dfn[maxn],low[maxn],cnt;

int n,m,ans;

bool cut[maxn];

struct node

{

    int next,to;

}edge[];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void add(int from,int to)

{

    edge[++jishu].next=head[from];

    edge[jishu].to=to;

    head[from]=jishu;

}

void tarjan(int now,int fa)

{

    dfn[now]=low[now]=++cnt;

    int child=;

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (!dfn[to]){

            tarjan(to,fa);

            low[now]=min(low[now],low[to]);

            if (low[to]>=dfn[now]&&now!=fa) cut[now]=;

            if (now==fa) child++;

        }

        low[now]=min(low[now],dfn[to]);

    }

    if (child>=&&now==fa) cut[now]=;

}

int main()

{

    n=read(),m=read();

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

    {

        int u=read(),v=read();

        add(u,v);add(v,u);

    }

    for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i,i);

    for (int i=;i<=n;i++) if (cut[i]) ans++;

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

    for (int i=;i<=n;i++) if (cut[i]) printf("%d ",i);

    return ;

}

巴特西

Tarjan算法学习笔记

最新文章

热门文章

巴特西

Tarjan算法 学习笔记

最新文章

热门文章

Tarjan算法学习笔记