广州网站建设 讯度网络万网注册域名查询官方网站
[图论与代数结构 701] 强连通分量
题目描述
给定一张 n n n 个点 m m m 条边的有向图，求出其所有的强连通分量。
注意，本题可能存在重边和自环。
输入格式
第一行两个正整数 n n n ， m m m ，表示图的点数和边数。
接下来 m m m 行，每行两个正整数 u u u 和 v v 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 ≤ n ≤ 10000 1 \le n \le 10000 1≤n≤10000， 1 ≤ m ≤ 100000 1 \le m \le 100000 1≤m≤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 n n 个点 m m m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式
第一行两个正整数 n , m n,m n,m
第二行 n n n 个整数，其中第 i i i 个数 a i a_i ai 表示点 i i i 的点权。
第三至 m + 2 m+2 m+2 行，每行两个整数 u , v u,v u,v，表示一条 u → v u\rightarrow v u→v 的有向边。
输出格式
共一行，最大的点权之和。
样例 #1
样例输入 #1
2 2
1 1
1 2
2 1
样例输出 #1
2
提示
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 4 1\le n \le 10^4 1≤n≤104， 1 ≤ m ≤ 1 0 5 1\le m \le 10^5 1≤m≤105， 0 ≤ a i ≤ 1 0 3 0\le a_i\le 10^3 0≤ai≤103。
我们对有向图进行缩点后，整个图就变为了DAG，即有向无环图，我们就可以在有向无环图上进行一些DP的操作，显然对于一个有向无环图，我们很容易得到这个题的状态转移：
d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s [ i ] ) ， s 为缩点后的点权， j 为 i 的前驱节点 dp[i]=max(dp[i],dp[j]+s[i])，s为缩点后的点权，j为i的前驱节点 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;
}