缩点（强连通分量）¶
缩点指的是将图中的一个连通分量（通常是点双连通分量或强连通分量）缩减为一个单一的顶点。对于强连通分量，它有这样的应用：
假设你可以从一个点出发，沿着有向图采集沿途点上的金币。那么当你进入一个强连通分量时，这个分量中的所有点你都可达。为了减低时间复杂度，我们可以把这个分量用一个点来代替。分量与外界的连边变成了这个点与其它点的连边。
例题 #1¶
给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
大意
子问题1：把同一个强连通分量里的所有点压缩成一个点即可。处理完后图中无环。
子问题2：在新的有向无环图中找最大路径。记忆化dfs搜索即可。
/*////////ACACACACACACAC///////////
. Coding by Ntsc .
. ToFind Chargcy .
. Prove Yourself .
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
#define ll long long
#define db double
#define rtn return
#define i1n int i=1;i<=n;i++
#define in1 int i=n;i>=1;i--
using namespace std;
const int N=5e5+5;
const int M=1e5;
const int Mod=1e5;
const int INF=1e5;
int dfn[N],low[N],stk[N],tot,top,cnt,scc[N],siz[N],sccw[N],w[N],dis[N],vis[N],n,m,way[N][2],instk[N],s,np,p[N],ans;
vector <int> e[N];
int f[N];
vector<int>e2[N];
void add(int a,int b){
e[a].push_back(b);
}
void add2(int a,int b){
e2[a].push_back(b);
}
void tarjan(int x){//强连通分量缩点
//入x时,时间戳追溯值更新,入栈
dfn[x]=low[x]=++tot;
stk[++top]=x;instk[x]=1;
for(int i=0;i<e[x].size();i++){//枚举x的邻点y
int y=e[x][i];
if(!dfn[y]){//如果y还没有访问过
tarjan(y);//向下走
low[x]=min(low[x],low[y]);//返回时更新
}else if(dfn[y]&&instk[y]){//说明 y被访问过 ->要么y是祖先(在x出通过返祖边访问到了),要么是左子树的点(在x通过横插边访问到了)
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){//说明x是这个强连通分量的根
int y;++cnt;
int flag=0;
do{
flag++;
y=stk[top--];instk[y]=0;
scc[y]=cnt;
++siz[cnt];
sccw[cnt]+=w[y];//记录缩点后强连通分量点的点权
} while(y!=x);
}
}
void dfs(int x){
if(f[x])return ;
f[x]=sccw[x];
int mx=0;
for(auto v:e2[x]){
if(!f[v])dfs(v);//搜过就不用再搜，直接调用
mx=max(mx,f[v]);
}
f[x]+=mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=m;i++){
cin>>way[i][0]>>way[i][1];
}
for(int i=1;i<=m;i++){
add(way[i][0],way[i][1]);
}
for(int i=1;i<=n;i++)//题目不保证图连续!
if(!dfn[i]) tarjan(i);
//建新图
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
int v=e[i][j];
if(scc[i]==scc[v])continue;//注意continue
add2(scc[i],scc[v]);//注意不是scc[j]
}
}
//求DAG中最大路径
for(int i=1;i<=cnt;i++){
if(f[i])continue;
dfs(i);
ans=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}
例题 #2 [ZJOI2007] 最大半连通子图¶
一个有向图 \(G=\left(V,E\right)\) 称为半连通的 (Semi-Connected)，如果满足：\(\forall u,v\in V\)，满足 \(u\to v\) 或 \(v\to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。
若 \(G'=\left(V',E'\right)\) 满足 \(V'\subseteq V\)，\(E'\) 是 \(E\) 中所有跟 \(V'\) 有关的边，则称 \(G'\) 是 \(G\) 的一个导出子图。若 \(G'\) 是 \(G\) 的导出子图，且 \(G'\) 半连通，则称 \(G'\) 为 \(G\) 的半连通子图。若 \(G'\) 是 \(G\) 所有半连通子图中包含节点数最多的，则称 \(G'\) 是 \(G\) 的最大半连通子图。
给定一个有向图 \(G\)，请求出 \(G\) 的最大半连通子图拥有的节点数 \(K\)，以及不同的最大半连通子图的数目 \(C\)。由于 \(C\) 可能比较大，仅要求输出 \(C\) 对 \(X\) 的余数。
输入格式
第一行包含两个整数 \(N,M,X\)。\(N,M\)分别表示图 \(G\) 的点数与边数，\(X\) 的意义如上文所述。
接下来 \(M\) 行，每行两个正整数 \(a,b\)，表示一条有向边 \(\left(a,b\right)\)。图中的每个点将编号为 \(1,2,3\dots N\)，保证输入中同一个\(\left(a,b\right)\)不会出现两次。
输出格式
应包含两行，第一行包含一个整数 \(K\)，第二行包含整数 \(C\bmod X\)。
对于 \(100\%\) 的数据，\(N\le 10^5\)，\(M\le 10^6\)，\(X\le 10^8\)。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this && dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename c, typename... A>
void err(T<c> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 1e5+5;
const int INF = 1e18;
const int M = 1e7;
int MOD = 1e9+7;
itn fa[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
vector<int> e[N],g[N];
void add(int a,int b){
e[a].pb(b);
}
int ind[N],stk[N],top,dfn[N],low[N],tim;
int sccCnt;
int scc[N];
int f[N];
int ans,mx;
int vis[N];
int instk[N];
int sz[N];
int iind[N];
int h[N];
map<int,map<int,bool>> con;
void addg(int a,int b){
if(con[a][b]||con[b][a])return ;
con[a][b]=1;
g[a].pb(b);
ind[b]++;
}
void tarjan(int x){
low[x]=dfn[x]=++tim;
stk[++top]=x;
instk[x]=1;
for(auto v:e[x]){
// if(v==fa)continue;
if(dfn[v]&&instk[v]){
low[x]=min(low[x],dfn[v]);
}else if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
}
if(low[x]==dfn[x]){
int y=0;
++sccCnt;
do{
y=stk[top--];
instk[y]=0;
sz[sccCnt]++;
scc[y]=sccCnt;
}while(y!=x);
}
}
void solve(){
int n=rd,m=rd,MOD=rd;
for(int i=1;i<=m;i++){
itn a=rd,b=rd;
add(a,b);
}
/*
向考虑缩点，之后再DAG上求解
在DAG上求半联通分量，先考虑dag dp，topo排序
一个半联通分量scc里一定有一个入度=0的点，我们称它位这个scc的根
设f_i 为以i为根的scc的大小，那么有
f_i=sz_i+\max_j\in son(i)f[j] 注意不是sum
将反图就有
f_i=sz_i+\max_j\in fa(i)f[j]
考虑求数量
令h_i为以i为根的scc的数量
*/
for(int i=1;i<=n;i++){
if(!dfn[i])
tarjan(i);
}
// for(int i=1;i<=n;i++)cdbg(scc[i]);
for(int i=1;i<=sccCnt;i++)fa[i]=i;
for(itn x=1;x<=n;x++){
for(auto v:e[x]){
if(scc[x]!=scc[v])addg(scc[v],scc[x]);
}
}
for(int i=1;i<=sccCnt;i++){
iind[i]=ind[i];
}
queue<int> q;
for(int i=1;i<=sccCnt;i++){
if(!ind[i])q.push(i);
}
while(q.size()){
int x=q.front();
f[x]+=sz[x];
q.pop();
vis[x]=1;
for(auto v:g[x]){
// if(vis[v])continue;
ind[v]--;
if(!ind[v])q.push(v);
f[v]=max(f[v],f[x]);
}
}
memset(vis,0,sizeof vis);
for(int i=1;i<=sccCnt;i++){
if(!iind[i])q.push(i),h[i]=1;
}
while(q.size()){
int x=q.front();
q.pop();
vis[x]=1;
for(auto v:g[x]){
// if(vis[v])continue;
iind[v]--;
if(!iind[v])q.push(v);
if(f[x]+sz[v]==f[v]){
h[v]+=h[x];
h[v]%=MOD;
}
}
}
for(int i=1;i<=sccCnt;i++){
mx=max(mx,f[i]);
}
for(int i=1;i<=sccCnt;i++){
if(f[i]==mx)ans+=h[i],ans%=MOD;
// cdbg(i,h[i]);
}
cout<<mx<<'\n'<<ans%MOD;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #3 [HAOI2010] 软件安装¶
题目描述
现在我们的手头有 \(N\) 个软件，对于一个软件 \(i\)，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\)。我们希望从中选择一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件 \(i\) 只有在安装了软件 \(j\)（包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依赖软件 \(j\))。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 \(0\)。
我们现在知道了软件之间的依赖关系：软件 \(i\) 依赖软件 \(D_i\)。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 \(D_i=0\)，这时只要这个软件安装了，它就能正常工作。
输入格式
第 1 行：\(N,M(0\leq N\leq 100, 0\leq M\leq 500)\)
第 2 行：\(W_1,W_2, ... W_i, ..., W_n (0\leq W_i\leq M)\)
第 3 行：\(V_1, V_2, ..., V_i, ..., V_n (0\leq V_i\leq 1000)\)
第 4 行：\(D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)\)
输出格式
一个整数，代表最大价值。
我们发现，如果连边后是一颗树，我们跑树形dp即可。但是我们发现本题可能会有循环依赖的情况，所以我们先scc缩点，然后再跑树形dp即可。
因为一个点只有一个父亲，所以是基环树森林，缩点后不会出现DAG。
空间要计算好。
对于有向图，连边方向别反了（包括缩点时）
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s << ' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
const int N = 3e3 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
vector<int> e[N],g[N];
int ind[N],out[N];
void addg(int a,int b){
g[a].push_back(b);
ind[b]++;
}
void add(int a,int b){
e[a].pb(b);
}
int f[N][N];//定义为考虑第i给软件，目前使用了的空间为j，其中是否安装i得到的最大价值
int v[N],w[N],d[N];
int n,m;
int dfn[N],low[N];
int tim;
int stk[N];
int instk[N];
int top;
int sccCnt;
int scc[N];
int sumw[N];
int sumv[N];
void tarjan(int x){
dfn[x]=low[x]=++tim;
instk[x]=1;
stk[++top]=x;
for(auto v:e[x]){
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}else if(instk[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(low[x]==dfn[x]){
int y;
sccCnt++;
do{
y=stk[top--];
instk[y]=0;
scc[y]=sccCnt;
sumw[sccCnt]+=w[y];
sumv[sccCnt]+=v[y];
}while(x!=y);
}
}
bool vis[N];
void dfs(int u) {
vis[u]=1;
for(int i = sumw[u]; i <= m; i++)
f[u][i] = sumv[u];
for(auto v:g[u]) {
if(vis[v])continue;
dfs(v); int k = m - sumw[u];
for(int i = k; i >= 0; i--)
for(int j = 0; j <= i; j++)
f[u][i + sumw[u]] = max(f[u][i + sumw[u]], f[v][j] + f[u][i + sumw[u] - j]);
}
}
void solve(){
n=rd,m=rd;
for(int i=1;i<=n;i++){
w[i]=rd;
}
for(int i=1;i<=n;i++){
v[i]=rd;
}
for(int i=1;i<=n;i++){
d[i]=rd;
if(d[i])add(d[i],i);//注意建图反向
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
int v=d[i];
if(scc[i]!=scc[v]){
addg(scc[v],scc[i]);//别连反！
}
}
for(int i=1;i<=sccCnt;i++){
if(!ind[i])addg(0,i);
}
dfs(0);
cout<<f[0][m]<<endl;
}
signed main() {
int T=1;
while(T--){
solve();
}
return 0;
}