今天学习一下缩点。
强连通的蓝题真水
luogu p2812
题意：
学校有n台计算机，他们之间有线路相连，我们视为有向边。
(1)问要使得所有计算机都能获取到一个消息，需要几台母机？
(2)如果用一台母机传播消息使得所有计算机都接收到，需要添加几条新的线路？
思路：
这个题是缩点的模板题。
首先通过tarjan的scc求得有向图中的环，每个环就相当于一个点，因为环内的每个点都可以任意到一个其他点。
简化有向图之后我们统计剩下点的入度和出度为零的点的数量，取最大值。
解释如图：
这三个图都需要练两条边。
注意还要特判一下如果只有一个联通量第二个数字是0
具体实现看代码（妙）：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top; // 栈的作用是记录正在访问的点
int scc[N], siz[N], cnt; //最后的结果是scc[i] = k 记录第i个节点在第k个强连通分量里，大小是siz【k】
int in[N], out[N];
void tarjan(int x) {
//入x时， 盖戳， 入栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x]) {
if(!dfn[y]) { //若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]); //回x时更新low
}
else if(instk[y]) { //若y已访问且在栈中
low[x] = min(low[x], low[y]);
}
// 剩下已经访问并且不在栈中的情况是y已经被访问完，不在枚举
}
//离x时，记录scc
if(dfn[x] == low[x]) { //若x是scc的根
int y; ++cnt;
do{ //陆续把强连通分量出栈
y = stk[top--]; instk[y] = 0;
scc[y] = cnt; //scc编号
++siz[cnt]; //scc大小
} while(y != x);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int t;
while(cin >> t && t) {
e[i].push_back(t);
}
}
for (int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
for (auto it : e[i]) {
if(scc[i] != scc[it]) {
in[scc[it]]++;
out[scc[i]]++;
}
}
}
int a = 0, b = 0;
for (int i = 1; i <= cnt; i++) {
a += (in[i] == 0);
b += (out[i] == 0);
}
cout << a << endl;
if(cnt == 1) {
cout << 0 << endl;
}
else {
cout << max(a, b) << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T--) {
solve();
}
return 0;
}
p2002
题意：
n个城市m条有向边，问从至少几个城市开始扩散消息能够把消息全部扩散。
思路：
很裸的缩点题，tarjan缩点之后统计入度为零的点就行了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top; // 栈的作用是记录正在访问的点
int scc[N], siz[N], cnt; //最后的结果是scc[i] = k 记录第i个节点在第k个强连通分量里，大小是siz【k】
int in[N], out[N];
void tarjan(int x) {
//入x时， 盖戳， 入栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x]) {
if(!dfn[y]) { //若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]); //回x时更新low
}
else if(instk[y]) { //若y已访问且在栈中
low[x] = min(low[x], low[y]);
}
// 剩下已经访问并且不在栈中的情况是y已经被访问完，不在枚举
}
//离x时，记录scc
if(dfn[x] == low[x]) { //若x是scc的根
int y; ++cnt;
do{ //陆续把强连通分量出栈
y = stk[top--]; instk[y] = 0;
scc[y] = cnt; //scc编号
++siz[cnt]; //scc大小
} while(y != x);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
for (auto ne : e[i]) {
if(scc[ne] != scc[i]) {
in[scc[ne]]++;
out[scc[i]]++;
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++) {
ans += (in[i] == 0);
}
cout << ans << endl;
return 0;
}
p2194
题意：
火烧情侣，回路的费用是一个点，其他的是相加，问费用最小。
思路：
用tarjan求强连通分量，把每个强连通分量的minm和cnt找出来，minm相加，cnt相乘取模就是答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
int mod = 1000000007;
vector<int>e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top; // 栈的作用是记录正在访问的点
int scc[N], siz[N], cnt; //最后的结果是scc[i] = k 记录第i个节点在第k个强连通分量里，大小是siz【k】
int cost[N];
int ans = 0, num = 1;
void tarjan(int x) {
//入x时， 盖戳， 入栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x]) {
if(!dfn[y]) { //若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]); //回x时更新low
}
else if(instk[y]) { //若y已访问且在栈中
low[x] = min(low[x], low[y]);
}
// 剩下已经访问并且不在栈中的情况是y已经被访问完，不在枚举
}
//离x时，记录scc
if(dfn[x] == low[x]) { //若x是scc的根
int minm = 1000000000, t = 0;
int y; ++cnt;
do{ //陆续把强连通分量出栈
y = stk[top--]; instk[y] = 0;
if(cost[y] < minm) {
t = 1;
minm = cost[y];
}
else if(cost[y] == minm) {
t++;
}
scc[y] = cnt; //scc编号
++siz[cnt]; //scc大小
} while(y != x);
ans += minm;
num = (num * t) % mod;
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> cost[i];
}
int m;
cin >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
cout << ans << " " << num << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T--) {
solve();
}
return 0;
}
luogu p2341
题意：
n个点，m条边的有向图，有向边 u -> v 表示u喜欢v，喜欢可以传递，找出被所有牛喜欢的牛的个数。
思路：
缩点，如果是环就相互喜欢，根据传递性可以表示成一个点，然后统计出度为0的强连通分量的个数，如果是1个，输出这个强连通分量的大小，反之输出0.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
vector<int>e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top; // 栈的作用是记录正在访问的点
int scc[N], siz[N], cnt; //最后的结果是scc[i] = k 记录第i个节点在第k个强连通分量里，大小是siz【k】
int in[N], out[N];
void tarjan(int x) {
//入x时， 盖戳， 入栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x]) {
if(!dfn[y]) { //若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]); //回x时更新low
}
else if(instk[y]) { //若y已访问且在栈中
low[x] = min(low[x], low[y]);
}
// 剩下已经访问并且不在栈中的情况是y已经被访问完，不在枚举
}
//离x时，记录scc
if(dfn[x] == low[x]) { //若x是scc的根
int y; ++cnt;
do{ //陆续把强连通分量出栈
y = stk[top--]; instk[y] = 0;
scc[y] = cnt; //scc编号
++siz[cnt]; //scc大小
} while(y != x);
}
}
void solve() {
int n;
cin >> n;
int m;
cin >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
map<pair<int, int>, bool>mp;
for (int i = 1; i <= n; i++) {
for (auto it : e[i]) {
if(scc[i] != scc[it]) {
in[scc[it]] ++;
out[scc[i]] ++;
}
}
}
vector<int>v;
for (int i = 1; i <= cnt; i++) {
if(!out[i]) {
v.push_back(i);
}
}
if(v.size() == 1) {
cout << siz[v[0]] << endl;
}
else {
cout << 0 << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T--) {
solve();
}
return 0;
}
p2746
和p2812一样的体型，魔改了一下题意而已。
标签：cnt,20,int,scc,2024,++,low,instk From： https://www.cnblogs.com/yyc4591/p/18024276