强连通分量+缩点

[图论与代数结构 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
2
3
4
5
6
7
8
9

样例输出 #1

3
1 2 5 6
3
4
1
2
3
4

提示

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

#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

【模板】缩点

题目描述

给定一个 $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
3
4

样例输出 #1

2
1

提示

对于 $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 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117