强连通分量+缩点

本文主要是介绍强连通分量+缩点，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

强连通分量+缩点

使用tarjan算法求强连通分量，再把强连通分量缩成一个点。

所需的数据结构

int dfn[10004];//遍历到i节点时的时间戳
int low[10004]；//i节点不通过父节点可以回溯到的最小时间戳
int book[10004];//表示i是否入栈
stack<int> s;

先读入点和边

cin >> n >> m;
for (int i = 1; i <= n; i++)
	cin >> power[i];
for (int i = 1; i <= m; i++)
{
	cin >> x[i] >> y[i];
	a[x[i]].push_back(y[i]);
}

因为图可能不连通，所以以多个点为根dfs

//dfn数组充当了标记数组
for (int i = 1; i <= n; i++)
	if (dfn[i] == 0)
		dfs(i);

最重要的是dfs函数

将遍历到的每个点都入栈，栈中的节点构成了祖先和儿子的关系

如果一个节点的子节点未访问过，则继续dfs（子节点），且更新low

如果一个节点的子节点访问过且在栈中(在栈中表明这个节点和它的子节点存在祖先和儿子的关系)，

该节点可以回溯到祖先节点，更新low

如果一个节点的dfn--low，说明

• 1,该节点无法通过子节点回溯到祖先节点，即不存在环，所以这一个节点为一个强连通分量。将这个节点出栈。
• 2，该节点通过子节点回溯到他自己，表示存在一个以该节点为起始点的环。环上的所有点可以被所称一个点。将栈中的节点出栈直到这个节点出去。

然后重建缩点后的图(有向无环图)

进行接下来的操作。

模板题

P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<map>
using namespace std;

int n, m, power[10004], x[100005], y[100005], t = 1, tot, col[10004], money[10004], ans;
vector<int> a[10004];
int dfn[10004];//遍历到i节点时的时间戳
int low[10004];//i节点不通过父节点可以回溯到的最小时间戳
int book[10004];//表示i是否入栈
stack<int> s;
int ind[10004];

void dfs(int x);
void getans(int x, int p);
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> power[i];
	for (int i = 1; i <= m; i++)
	{
		cin >> x[i] >> y[i];
		a[x[i]].push_back(y[i]);
	}
	for (int i = 1; i <= n; i++)
		if (dfn[i] == 0)
			dfs(i);
	//重新建立缩点后的图
	for (int i = 1; i <= n; i++)
		a[i].clear();
	for (int i = 1; i <= m; i++)
	{
		if (col[x[i]] != col[y[i]]) //如果两个点不在一个连通分量中，则连边(两个点可能连多条相同的边)
		{
			a[col[x[i]]].push_back(col[y[i]]);
			ind[col[y[i]]]++;
		}
	}
	//dfs求具体的数据
	memset(book, 0, sizeof(book));
	for (int i = 1; i <= tot; i++)
	{
		if (ind[i] == 0)
		{
			book[i] = 1;
			getans(i, money[i]);
		}
	}
	cout << ans;
	return 0;
}
void dfs(int x)
{
	s.push(x);//将x入栈
	dfn[x] = t; low[x] = t; t++;//初始化
	book[x] = 1;//表明x已经入栈
	int len = a[x].size();
	for (int i = 0; i < len; i++)
	{
		if (dfn[a[x][i]] == 0)//如果子节点未被搜索过，继续搜索
		{
			dfs(a[x][i]);
			low[x] = min(low[x], low[a[x][i]]);//x节点如果能通过子节点走到dfn小的祖先，更新
		}
		if (dfn[a[x][i]] != 0 && book[a[x][i]] == 1)//子节点搜索过，且在栈内
		{
			low[x] = min(low[x], dfn[a[x][i]]);
		}
	}
	if (dfn[x] == low[x])//x为强连通块的根
	{
		tot++;//tot为强连通的编号
		while (s.top() != x)
		{
			col[s.top()] = tot;
			book[s.top()] = 0;
			money[tot] += power[s.top()];
			s.pop();
		}
		col[s.top()] = tot;
		book[s.top()] = 0;
		money[tot] += power[s.top()];
		s.pop();
	}
}
void getans(int x, int p)
{
	ans = max(ans, p);
	int len = a[x].size();
	for (int i = 0; i < len; i++)
	{
		if (book[a[x][i]] == 0)
		{
			book[a[x][i]] = 1;
			getans(a[x][i], p + money[a[x][i]]);
			book[a[x][i]] = 0;
		}
	}
}

这篇关于强连通分量+缩点的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！