P3387 【模板】缩点 Tarjan强连通分量/树上dp

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

首先，什么是强连通分量

极大强连通子图 叫做强连通分量

            首先要明确，

                    1. 极大强连通子图肯定是连通的，

                    2.若在增加一个结点，他们所构成的图将不是连通的

                    3.若该有向图是强连通图，那么其极大强连通子图就是他本身

                        (那么其强连通分量就为一，也就是说有几个极大强连通子图就有几个强连通分量)

                    4.非强连通图有多个极大强连通子图
————————————————
版权声明：本文为CSDN博主「爱叨叨的小嘟」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/L_Z_jay/article/details/112289485

所谓缩点，就是将有向有环图中的网或者环结构合并看作一个点，使原图称为DAG（有向无环图）以便对图进行操作，如求最长路最短路等等。

所以我们的主要思路就是，求出这个有向有环图中的强连通分量，并将其合并成一个代表点，之后重新组成一个DAG，对这个DAG求最长路。

而求强连通分量用到了Tarjan算法，之后再详细写一篇博客总结。其主要思路就是设置一个dfs顺序的数组dfn和一个表示该节点可以到达的dfn最小的节点的顺序数组low

当dfn[i]==low[i]的时候，说明这个i点可以重新回到i，简单说可以看作构成了一个环或者网状结构。如果保证这个环或网已经是最大的了，那么也就找到了一个强连通分量。

#include 
#include
#include
using namespace std;
#pragma warning(disable:4996);
#define ll long long
#define	int ll
#define rep(j,b,e) for(register int j=b;j<=e;j++)
#define drep(j,e,b) for(register int j=(e);j>=(b);j--)
int T = 1;
const int N = 2e5 + 10;
const int mod = 10000;
int n, m, k, q;
template <class T, class ...Arg>
void inline pln(T t, Arg ...args);//打印一行参数
template<typename T>
void inline pln(vector a, string s = " ");
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args);//输入一行数据
 
//--------------------------------------
 
struct edge {
	int from, to;
}edg[N];
int val[N];
int dfn[N];//dfs顺序
int low[N];//最早能回溯到的时间
vector<int>gra[N];//原图
vector<int>DAG[N];//之后构建的新图
vector<int>stk, inStk(N);//存储节点
vector<int>pre(N);//表示强连通分量的代表节点
int Time = 0;//记录dfs顺序
void Tarjan(int now) {
	dfn[now] = low[now] = ++Time;//“递”的时候初始化dfs顺序
	stk.push_back(now);
	inStk[now] = 1;
	for (auto& nx : gra[now]) {
		if (dfn[nx] == 0) {
			Tarjan(nx);
			low[now] = min(low[now], low[nx]);// 如果子节点可以回到更早的
			//地方那么now也可以回到。
		}
		else if (inStk[nx]) {//如果这个点还在栈中，则松弛一次
			low[now] = min(low[now], dfn[nx]);
		}
	}
	if (dfn[now] == low[now]) {//找到了一个强连通分量
		int x = -1;
		do {
			x = stk.back();
			stk.pop_back();
			inStk[x] = 0;
			pre[x] = now;//将强连通分量的元素值加到一个代表元素上
			//使环看作一个点，包括了独立的单个节点
		} while (x != now);
 
	}
}
vector<int>dp(N, 0);
int dfs(int now) {//求缩点完的DAG的最长路，树上dp求每点的最长路
	if (dp[now])return dp[now];
	int res = 0;
	for (auto nx : DAG[now]) {
		res = max(res, dfs(nx));
	}
	return dp[now] = res + val[now];
}
void init(int n) {//并查集类似的初始化
	rep(j, 1, n)pre[j] = j;
}
signed main()
{
#ifndef ONLINE_JUDGE
	//freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0); cout.tie(0);
	inln(n, m);
	init(n);
	rep(j, 1, n) {
		cin >> val[j];
	}
	rep(j, 1, m) {
		int f, t;
		cin >> f >> t;
		edg[j] = { f,t };
		gra[f].push_back(t);
	}
	rep(j, 1, n) {
		if (dfn[j] == 0)
			Tarjan(j);
	}
 
	rep(j, 1, n) {
		if (pre[j] != j) {//子节点j的值加到父节点，缩点
			val[pre[j]] += val[j];
		}
	}
	rep(j, 1, m) {
		auto [f, t] = edg[j];
		if (pre[f] == pre[t])//如果是一个环内的跳过
			continue;
		else {//因为代表点代替了强连通分量，新图建立全依靠代表节点
			DAG[pre[f]].push_back(pre[t]);
		}
	}
	int ans = 0;
	rep(j, 1, n) {
		ans = max(ans, dfs(j));
	}
	pln(ans);
	return 0;
}
 
//--------------------------------------
void inline  inln() {}
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args) {
	cin >> t;
	inln(args...);
}
void inline pln() {
	cout << "\n";
}
template <class T, class ...Arg>
void inline pln(T t, Arg ...args) {
	cout << t << " ";
	pln(args...);
}
template<typename T>
void inline pln(vector a, string s) {
	for (T& x : a) {
		cout << x << s;
	}
	cout << endl;
}

一.缩点应用

 如果是DAG，对整个图来一个动态规划即可。也就是对每个点记忆化搜索。取最值。但是此题图中可能存在环，所以采用缩点的思路将环合并为一个点。从题目来看，这个环应该合并为这个环内编号最大的点。合并完后重新建图即可。

#include 
#include
#include
using namespace std;
#pragma warning(disable:4996);
#define ll long long
#define	int ll
#define rep(j,b,e) for(register int j=b;j<=e;j++)
#define drep(j,e,b) for(register int j=(e);j>=(b);j--)
int T = 1;
const int N = 2e5 + 10;
const int mod = 10000;
int n, m, k, q;
 
template <class T, class ...Arg>
void inline pln(T t, Arg ...args);//打印一行参数
template<typename T>
void inline pln(vector a, string s = " ");
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args);//输入一行数据
//-------------------------------------
 
struct edge {
	int f, t;
}edg[N];
 
int dfn[N] = { 0 };
int low[N] = { 0 };
vector<int>gra[N];
vector<int>DAG[N];
vector<int>stk;
vector<int>inStk;
vector<int>pre;//存储祖先
vector<int>Max;//保存缩点完每个点的编号最大值，初始化为自身
vector<int>vis;
vector<int>ans;
int Time = 0;
 
void tarjan(int now) {
	dfn[now] = low[now] = ++Time;
	stk.push_back(now);
	inStk[now] = 1;
	for (auto nx : gra[now]) {
		if (dfn[nx] == 0) {
			tarjan(nx);
			low[now] = min(low[now], low[nx]);
		}
		else if (inStk[nx]) {
			low[now] = min(low[now], dfn[nx]);
		}
	}
	if (dfn[now] == low[now]) {
		int x = -1;
		int mx = 0;
		do {
			x = stk.back();
			stk.pop_back();
			inStk[x] = 0;
			mx = max(x, mx);
			pre[x] = now;
		} while (x != now);
		Max[now] = max(Max[now], mx);//保存环中的最大值
	}
}
void newDAG() {//新图
	rep(j, 1, n) {
		if (dfn[j] == 0)
			tarjan(j);
	}
	rep(j, 1, m) {
		auto [f, t] = edg[j];
		if (pre[f] != pre[t]) {
			DAG[pre[f]].push_back(pre[t]);
		}
	}
 
}
int dfs(int now) {
	if (ans[now])return ans[now];
	int res = Max[now];
	for (auto nx : DAG[now]) {
		res = max(res, dfs(nx));
	}
	return ans[now] = res;
}
 
 
signed main()
{
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0); cout.tie(0);
	Max.assign(N, 0);
	vis.assign(N, 0);
	ans.assign(N, 0);
	pre.assign(N, 0);
	inStk.assign(N, 0);
	inln(n, m);
 
	rep(j, 1, m) {
		int f, t;
		inln(f, t);
		edg[j] = { f,t };
		gra[f].push_back(t);
	}
	rep(j, 1, n)Max[j] = j;
	rep(j, 1, n)pre[j] = j;
	newDAG();
	rep(j, 1, n) {
		if (ans[j] == 0)
			dfs(j);
	}
	rep(j, 1, n) {
		cout << ans[pre[j]] << " ";
	}
	return 0;
}
 
//--------------------------------------
void inline  inln() {}
template<class T, class ...Arg>
void inline  inln(T& t, Arg&...args) {
	cin >> t;
	inln(args...);
}
void inline pln() {
	cout << "\n";
}
template <class T, class ...Arg>
void inline pln(T t, Arg ...args) {
	cout << t << " ";
	pln(args...);
}
template<typename T>
void inline pln(vector a, string s) {
	for (T& x : a) {
		cout << x << s;
	}
	cout << endl;
}