tarjan算法（强连通分量 + 强连通分量缩点 + 桥(割边) + 割点 + LCA）

这篇文章是从网络上总结各方经验以及自己找的一些例题的算法模板,主要是用于自己的日后的模板总结以后防失忆常看看的, 写的也是自己能看懂即可。

tarjan算法的功能很强大, 可以用来求解强连通分量,缩点,桥,割点,LCA等,日后写到相应的模板题我就会放上来。

1.强连通分量(分量中是任意两点间都可以互相到达)

按照深度优先遍历的方式遍历这张图。
遍历当前节点所出的所有边。在遍历过程中：

( 1 ) 如果当前边的终点还没有访问过，访问。

回溯回来之后比较当前节点的low值和终点的low值。将较小的变为当前节点的low值。（因为遍历到终点时有可能触发了2）

( 2 ) 如果已经访问过，那我们一定走到了一个之前已经走过的点（终点的时间戳一定比当前的小）

则比较当前节点的low值和终点的dfn值。将较小的变为当前节点的low值
在回溯过程中，对于任意节点u用其出边的终点v的low值来更新节点u的low值。因为节点v能够回溯到的已经在栈中的节点，节点u也一定能够回溯到。因为存在从u到v的直接路径，所以v能够到的节点u也一定能够到。
当一个节点的dfn值和low值相等时，这个节点是一个强联通分量的“根”。压栈，输出。

例题：http://acm.hdu.edu.cn/showproblem.php?pid=1269

#include<stdio.h>

#include<stack>

#include<algorithm>

#include<string.h>

using namespace std;

int n, m, cnt, deep, kinds_color;

int head[10000 + 10];

int dfn[10000 + 10], low[10000 + 10], vis[10000 + 10];

stack<int>S;

struct Edge

{

	int to, next;

}edge[100000 + 10];

void add(int u, int v)

{

	edge[++ cnt].to = v;

	//edge[cnt].w = w;

	edge[cnt].next = head[u];

	head[u] = cnt;

}

void tarjan(int now)

{

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

	S.push(now);

	vis[now] = 1;

	for(int i = head[now]; i != 0; 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])

	{

		kinds_color ++;

		while(1)

		{

			int temp = S.top();

			S.pop();

			if(temp == now)

				break;

		}

	}

}

int main()

{

	int a, b;

	while(scanf("%d%d", &n, &m)!=EOF)

	{

		if(n == 0 && m == 0)

			break;

		cnt = deep = kinds_color = 0;

		memset(head, 0, sizeof(head));

		memset(dfn, 0, sizeof(dfn));

		memset(vis, 0, sizeof(vis));

		memset(low, 0, sizeof(low));

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

		{

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

			add(a, b);

		}

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

			if(!dfn[i])

				tarjan(i);

		if(kinds_color == 1)

			printf("Yes\n");

		else

			printf("No\n");

	}

	return 0;

}

2.强连通分量缩点(多了步化简图的操作)

主要步骤跟上面求分量是一模一样的,区别在于需要在栈出的过程中,记录每个点所处的哪个分量

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

{

    k_color ++; //分块

    while(1)

    {

        int temp = S.top();

        S.pop();

        color[temp] = k_color; //记录每个点所属的分量块

        vis[temp] = 0;

        if(temp == now)

            break;

    }

}

for(int i = 1; i <= n; i ++)//遍历原图

{

    for(int j = head[i]; j != -1; j = edge[j].next)

    {

        int to = edge[j].to;

        int x = color[i], y = color[to];//x, y为强连通分量的编号

        if(x != y)//如果起点终点属于不同的连通分量,就可以建为新图的边了,点为连通分量编号

        {

            add1(x, y);

        //    in[y] ++;这是拓扑排序的入度 无视掉

        }

    }

}

3.tarjan求割点

例题：https://www.luogu.org/problemnew/show/P3388

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

int n, m, ans;

int cnt, head[20010];

int dfn[20010], low[20010], deep;

int flag[20010];

struct Edge

{

    int to, next;

}edge[100010 * 2];

void add(int a, int b)

{

    edge[++ cnt].to = b;

    edge[cnt].next = head[a];

    head[a] = cnt;

}

void tarjan(int now, int root) //求割点是不需要栈结构的

{

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

    int child = 0;//根节点的特判

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

    {

        int to = edge[i].to;

        if(!dfn[to])

        {

            tarjan(to, root);

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

            if(low[to] >= dfn[now] && now != root)//表示该节点绕不回上面 ,那么上面的点是割点,因为去割掉之后下面的点就与上面的点分离了

            {

                flag[now] = 1;

            }

            if(now == root)//求根节点的子树数量

                child ++;

        }

        low[now] = min(low[now], dfn[to]);//注意是dfn

    }

    if(child >= 2 && now == root) //如果根节点的子树数量大于等于2 ,将根节点去掉之后两颗子树就分离了

    {

        flag[now] = 1;

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    cnt = deep = ans = 0;

    mem(head, -1);

    mem(dfn, 0);

    mem(low, 0);

    mem(flag, 0);

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

    {

        int a, b;

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

        add(a, b);

        add(b, a);

    }

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

        if(!dfn[i])

            tarjan(i, i);

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

        if(flag[i])

            ans ++;

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

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

        if(flag[i])

            printf("%d ", i);

    return 0;

}

　4.求无向图的割边/桥

割边:在一个无向图中,去掉一条边(u, v),可以使图的连通分量增多的边, 就是割边,也称做桥

原理：利用tarjan算法, 对于一条边的起点u,终点v,如果满足条件 low[v] > dfn[u], 那么(u, v)就是一条割边, 因为这意味着不存在其他的边使得v可以回到u, 那么割掉就使图分离了.

需要注意的是跟割点不同, 没有等于号, 否则说明存在其他边回到起点, 那么就不是割边。

还有一点与割点不同, tarjan(int now, int pre),这里第二个变量记录的不是遍历起点的根节点, 而是记录now的父亲节点pre, 这样的话可以通过if(to != pre)保证不往回指,因为这是个无向图, 前向星会存回边.

例题：https://www.luogu.org/problemnew/show/P1656

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

int n, m, sum;

int head[200], cnt;//链式前向星数组

int dfn[200], low[200], deep;//tarjan数组 

struct Edge

{

	int from, to, next;

}edge[5000 * 2];

void add(int a, int b)

{

	edge[++ cnt].to = b;

	edge[cnt].from = a;

	edge[cnt].next = head[a];

	head[a] = cnt;

}

struct ANS

{

	int from, to;

}ans[5000 * 2];

bool cmp(ANS a, ANS b)

{

	if(a.from != b.from)

		return a.from < b.from;

	else

		return a.to < b.to;

}

void tarjan(int now, int pre)

{

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

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

	{

		int to = edge[i].to;

		if(!dfn[to])

		{

			tarjan(to, now);//pre指向now

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

			if(low[to] > dfn[now])

			{

				ans[++ sum].from = edge[i].from;

				ans[sum].to = to;

			}

		}

		else if(to != pre)

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

	}

}

int main()

{

	scanf("%d%d", &n, &m);

	cnt = deep = sum = 0;

	mem(head, -1), mem(dfn, 0), mem(low, 0);

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

	{

		int a, b;

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

		add(a, b);

		add(b, a);

	}

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

		if(!dfn[i])

			tarjan(i, -1);

	sort(ans + 1, ans + 1 + sum, cmp);

	for(int i = 1; i <= sum; i ++)

		printf("%d %d\n", ans[i].from, ans[i].to);

}

秒客网

tarjan算法（强连通分量 + 强连通分量缩点 + 桥(割边) + 割点 + LCA）

相关文章