强连通分量+缩点

[图论与代数结构 701] 强连通分量

题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，求出其所有的强连通分量。

注意，本题可能存在重边和自环。

输入格式

第一行两个正整数 $n$ ， $m$ ，表示图的点数和边数。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条边。

输出格式

第一行一个整数表示这张图的强连通分量数目。

接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。

样例 #1

样例输入 #1

6 8
1 2
1 5
2 6
5 6
6 1
5 3
6 4
3 4

样例输出 #1

3
1 2 5 6
3
4

提示

对于所有数据，$1\le n\le 10000$，$1\le m\le 100000$。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,m,tot,dfsn[N],ins[N],low[N];
stack<int> s;vector<int> e[N];
vector< vector<int> > scc;
vector<int> b(N);
void dfs(int x)
{low[x]=dfsn[x]=++tot,ins[x]=1,s.push(x);for(auto u: e[x]){if(!dfsn[u]){dfs(u);low[x]=min(low[x],low[u]);}else if(ins[u]) low[x]=min(low[x],dfsn[u]);}if(dfsn[x]==low[x]){vector<int> c;while(1){auto t=s.top();c.push_back(t);ins[t]=0;s.pop();b[t]=scc.size();if(t==x) break;}sort(c.begin(),c.end());scc.push_back(c);}
}void add(int u,int v)
{e[u].push_back(v);
}void solve()
{	int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v);}for(int i=1;i<=n;i++){if(!dfsn[i]){dfs(i);}}cout<<scc.size()<<endl;vector<int> vis(N);for(int i=1;i<=n;i++){int x=b[i];if(vis[x]) continue;vis[x]=1;for(auto r: scc[x]) cout<<r<<" ";cout<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

【模板】缩点

题目描述

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

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

输入格式

第一行两个正整数 $n,m$

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\to v$ 的有向边。

输出格式

共一行，最大的点权之和。

样例 #1

样例输入 #1

2 2
1 1
1 2
2 1

样例输出 #1

2

提示

对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 10^5$，$0\le a_i\le 10^3$。

我们对有向图进行缩点后，整个图就变为了DAG，即有向无环图，我们就可以在有向无环图上进行一些DP的操作，显然对于一个有向无环图，我们很容易得到这个题的状态转移：
$$dp[i]=max(dp[i],dp[j]+s[i])，s为缩点后的点权，j为i的前驱节点$$

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"int n, m, tot, dfsn[N], ins[N], low[N];
stack<int> s;
vector<int> e[N], e2[N];
vector<vector<int>> scc;
vector<int> b(N);
int a[N],z[N];void dfs(int x)
{low[x] = dfsn[x] = ++tot, ins[x] = 1, s.push(x);for (auto u : e[x]){if (!dfsn[u]){dfs(u);low[x] = min(low[x], low[u]);}else if (ins[u])low[x] = min(low[x], dfsn[u]);}if (dfsn[x] == low[x]){vector<int> c;while (1){auto t = s.top();c.push_back(t);ins[t] = 0;s.pop();b[t] = scc.size();z[scc.size()]+=a[t];if (t == x)break;}scc.push_back(c);}
}void add(int u, int v)
{e[u].push_back(v);
}void solve()
{cin >> n >> m ;for(int i=1;i<=n;i++) cin>>a[i];for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;add(u, v);}for (int i = 1; i <= n; i++){if (!dfsn[i]){dfs(i);}}for(int i=1;i<=n;i++){for(auto u: e[i]){if(b[i]!=b[u]){e2[b[i]].push_back(b[u]);}}}vector<int> dp(N);vector<int> vis(N);int t=0;for(int i=0;i<scc.size();i++){dp[i]=z[i];}for(int i=scc.size()-1;i>=0;i--){t++;for(auto u: e2[i]){if(vis[u]!=t){vis[u]=t;if(dp[u]<dp[i]+z[u]){dp[u]=dp[i]+z[u];}}}}int ans=0;for(int i=0;i<scc.size();i++){ans=max(ans,dp[i]);}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin>>t;while (t--){solve();}system("pause");return 0;
}