知识总结
Tarjan 算法
Tarjan 算法是一种用于计算有向图中强连通分量的算法。
Tarjan 算法的基本思想是：
- 首先，将图中每个节点标记为未访问。
- 然后，从某个节点开始，对该节点进行 DFS，并记录该节点的入度（即该节点的邻居个数）。
- 对于每个节点，如果其入度为 0，则说明它是一个根节点，将它标记为已访问，并将它加入栈中。
- 然后，从栈中弹出一个节点，并对该节点进行 DFS，并记录该节点的入度。
- 对于每个节点，如果其入度为 0，则说明它是一个根节点，将它标记为已访问，并将它加入栈中。
- 重复上述步骤，直到栈为空。
Tarjan 算法的运行时间复杂度为 \(O(n+m)\)，其中 \(n\) 是节点数，\(m\) 是边数。
缩点
缩点是一种对图进行预处理的技术，目的是减少搜索空间，提高算法效率。
缩点的基本思想是：
- 首先，将图中每个节点标记为未访问。
- 然后，对每个节点进行 DFS，并记录该节点的入度（即该节点的邻居个数）。
- 对于每个节点，如果其入度为 0，则说明它是一个根节点，将它标记为已访问，并将它加入栈中。
- 然后，从栈中弹出一个节点，并对该节点进行 DFS，并记录该节点的入度。
- 对于每个节点，如果其入度为 0，则说明它是一个根节点，将它标记为已访问，并将它加入栈中。
- 重复上述步骤，直到栈为空。
- 最后，对每个节点进行编号，并将每个节点的邻居划分到不同的集合中。
缩点的运行时间复杂度为 \(O(n+m)\)，其中 \(n\) 是节点数，\(m\) 是边数。
题目
T1 缩点
时间限制: 1000ms
空间限制: 125000kB
题目描述
给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式
第一行两个正整数 \(n,m\)
第二行 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 表示点 \(i\) 的点权。
第三至 \(m+2\) 行，每行两个整数 \(u,v\)，表示一条 \(u→v\) 的有向边。
输出格式
共一行，最大的点权之和。
样例
Input 1
2 2
1 1
1 2
2 1
Output 1
2
数据范围
- \(1≤n≤10^4\)
- \(1≤m≤10^5\)
- \(0≤a_i≤10^3\)
思路解析
缩点的模板题。
题目中因为没有限制走过的边不能走，所以如果在一个强连通分量里，这个强连通分量里的每个点都可以加到(ans)里，所以我们只要把每个强连通分量缩成一个点，再搜索就行了。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
bool vis[N];
int n, m, a[N], dp[N], low[N], dfn[N], start[N], to[N], cnt, deg[N], sum, ans, color[N], num[N], du[N], siz[N];
vector<int> v[N], v_new[N];
stack<int> st;
inline void Tarjan(int x) {
vis[x] = true;
low[x] = dfn[x] = ++cnt;
st.push(x);
for (auto i : v[x]) {
if (dfn[i] == 0) {
Tarjan(i);
low[x] = min(low[x], low[i]);
} else if (vis[i]) {
low[x] = min(dfn[i], low[x]);
}
}
if (low[x] == dfn[x]) {
int t = 0;
do {
t = st.top();
st.pop();
vis[t] = false;
color[t] = x;
siz[x] += a[t];
} while (x != t);
}
return;
}
void toposort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (!deg[i] && color[i] == i) {
q.push(i);
dp[i] = siz[i];
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto i : v_new[u]) {
if (!(--deg[i])) {
q.push(i);
}
dp[i] = max(dp[i], dp[u] + siz[i]);
}
}
return;
}
inline void input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> start[i] >> to[i];
v[start[i]].push_back(to[i]);
}
return;
}
inline void init() {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
Tarjan(i);
}
}
for (int i = 1; i <= m; i++) {
if (color[start[i]] != color[to[i]]) {
v_new[color[start[i]]].push_back(color[to[i]]);
deg[color[to[i]]]++;
}
}
return;
}
inline void print() {
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
cout << ans;
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
init();
toposort();
print();
return 0;
}
T2 行星与王国
题目描述
一款游戏有n个行星，由m个传送门连接。当且仅当两个行星a和b之间存在一条从a到b和从b到a的路径时，它们属于同一个王国。你的任务是确定每个行星所属的王国。
输入格式
第一行输入两个整数n和m：行星和传送门的数量。行星编号为1,2,...,n。接下来的m行描述了传送门。每行有两个整数a和b：你可以通过传送门从行星a到行星b旅行。
输出格式
首先打印一个整数k：王国的数量。然后，为每个行星打印一个介于1和k之间的王国标签。可以打印任何有效的解决方案。
样例
Input 1
5 6
1 2
2 3
3 1
3 4
4 5
5 4
Output 1
2
1 1 1 2 2
数据范围
1 ≤ n ≤ 10^5, 1 ≤ m ≤ 2 × 10^5, 1 ≤ a, b ≤ n
样例解释
行星1、2和3属于王国1，行星4和5属于王国2。
思路解析
缩点的模板题。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int> v[N];
bool vis[N];
int dfn[N], low[N], color[N], cnt, n, m, num;
stack<int> st;
void Tarjan(int x) {
vis[x] = true;
low[x] = dfn[x] = ++cnt;
st.push(x);
for (auto i : v[x]) {
if (!dfn[i]) {
Tarjan(i);
low[x] = min(low[x], low[i]);
} else if (vis[i]) {
low[x] = min(dfn[i], low[x]);
}
}
if (low[x] == dfn[x]) {
num++;
int t = 0;
do {
t = st.top();
st.pop();
vis[t] = false;
color[t] = num;
} while (x != t);
}
}
void input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int start, to;
cin >> start >> to;
v[start].push_back(to);
}
}
void init() {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
Tarjan(i);
}
}
}
void print() {
cout << num << endl;
for (int i = 1; i <= n; i++) {
cout << color[i] << " ";
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
init();
print();
return 0;
}
T3 无向图的连通分量
题目描述：
给出一个无向图，求图的连通分量的个数。保证无重边和自环。
输入格式：
第一行两个正整数 n（节点数），m（边数）。（节点编号从 1 到 n）
以下 m 行每行一个整数对描述一条边
输出格式：
一个整数表示连通分量的个数
样例输入：
8 7
1 2
2 3
3 1
4 5
4 6
4 7
4 8
样例输出：
2
数据范围：
1 ≤ n, m ≤10000
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int> v[N];
bool vis[N];
int color[N], cnt, n, m;
void dfs(int x, int col) {
vis[x] = true;
color[x] = col;
for (auto i : v[x]) {
if (!vis[i]) {
dfs(i, col);
}
}
}
void input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int start, to;
cin >> start >> to;
v[start].push_back(to);
v[to].push_back(start); // 因为是无向图，所以需要双向添加边
}
}
void init() {
cnt = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cnt++;
dfs(i, cnt);
}
}
}
void print() {
cout << cnt << endl;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
init();
print();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int> v[N];
bool vis[N];
int color[N], cnt, n, m;
void dfs(int x, int col) {
vis[x] = true;
color[x] = col;
for (auto i : v[x]) {
if (!vis[i]) {
dfs(i, col);
}
}
}
void input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int start, to;
cin >> start >> to;
v[start].push_back(to);
v[to].push_back(start); // 因为是无向图，所以需要双向添加边
}
}
void init() {
cnt = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cnt++;
dfs(i, cnt);
}
}
}
void print() {
cout << cnt << endl;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
init();
print();
return 0;
}
T4 最大半联通子图
题目描述
代码实现
#include <bits/stdc++.h>
using namespace std;
struct ppp {
int x, y;
} e[2000301];
struct node {
int to, from, next;
} edgef[2000301], edges[2000301];
int n, m, x, y, top, cnt, num, timetag, mo, ans1, ans2;
int dis[1000001], ans[1000001], headf[1000001], heads[1000001];
int zh[1000001], size[1000001], b[1000001];
int order[1000001], low[1000001], root[1000001], r[1000001], c[1000001];
bool cmp(ppp x, ppp y) {
return x.x == y.x ? (x.y < y.y) : (x.x < y.x);
}
inline void addf(int u, int v) {
edgef[++cnt].to = v;
edgef[cnt].from = u;
edgef[cnt].next = headf[u];
headf[u] = cnt;
}
inline void adds(int u, int v) {
edges[++cnt].to = v;
edges[cnt].next = heads[u];
heads[u] = cnt;
}
void tarjan(int t) {
order[t] = low[t] = ++timetag;
zh[++top] = t;
b[t] = 1;
int temp;
for (int i = headf[t]; i; i = edgef[i].next) {
if (!order[edgef[i].to]) {
tarjan(edgef[i].to);
low[t] = min(low[edgef[i].to], low[t]);
} else if (b[edgef[i].to])
low[t] = min(low[t], order[edgef[i].to]);
}
if (low[t] == order[t]) {
while ((temp = zh[top--])) {
b[temp] = 0;
root[temp] = t;
++size[t];
if (t == temp)
break;
}
}
}
void topsort() {
queue<int> q;
cnt = 0;
for (int i = 1; i <= num; i++)
if (e[i].x != e[i - 1].x || e[i].y != e[i - 1].y) {
adds(e[i].x, e[i].y);
++r[e[i].y];
++c[e[i].x];
}
for (int i = 1; i <= n; i++)
if (root[i] == i && !r[i])
q.push(i), dis[i] = size[i], ans[i] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = heads[t]; i; i = edges[i].next) {
if (dis[edges[i].to] < dis[t] + size[edges[i].to])
dis[edges[i].to] = dis[t] + size[edges[i].to], ans[edges[i].to] = ans[t];
else if (dis[edges[i].to] == dis[t] + size[edges[i].to])
ans[edges[i].to] = (ans[edges[i].to] % mo + ans[t] % mo) % mo;
--r[edges[i].to];
if (!r[edges[i].to])
q.push(edges[i].to);
}
}
for (int i = 1; i <= n; i++)
if (root[i] == i && !c[i]) {
if (dis[i] == ans1)
ans2 = (ans2 % mo + ans[i] % mo) % mo;
if (dis[i] > ans1)
ans1 = dis[i], ans2 = ans[i];
}
}
signed main() {
scanf("%d%d%d", &n, &m, &mo);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
addf(x, y);
}
for (int i = 1; i <= n; i++)
if (!order[i])
tarjan(i);
for (int i = 1; i <= m; i++) {
if (root[edgef[i].from] != root[edgef[i].to]) {
e[++num].x = root[edgef[i].from];
e[num].y = root[edgef[i].to];
}
}
sort(e + 1, e + num + 1, cmp);
topsort();
printf("%d\n%d", ans1, ans2);
return 0;
}
T5 大比萨
Uolevi的家人打算订购一张大比萨，并一起吃。共有 n 个家庭成员将参加订购，有 m 个可能的配料。比萨可以有任意数量的配料。每个家庭成员都会提出两个关于配料的愿望。这些愿望的形式是“配料 x 是好的/坏的”。您的任务是选择配料，使得每个人的两个愿望中至少有一个被满足（包含了一个好的配料或者不包含一个坏的配料）。
思路解析
法1：2-SAT
模板
法2：Tarjan
tarjan做法：这个问题被称为 2-sat。2-sat 解法的主要思想是：将 ai=x 这个命题当成一个点，这个命题当成一个点，则总共有2n个点。每一组限制可以理解拆解为两个限制,若已知ai!=x,则aj=y。因此每个限制是一个“推理”关系：若某个点的命题成立，则另一个点的命题也成立。如果以此为基础建图，那么强连通分量的意义是：这个分量的命题要么都成立，要么都不成立。
通过这个图结构，可以求解出结果。
法3：贪心
但这题可以贪心。如果有人两个要求都不满足时，我们尽量满足每人的的条件一，如果满足不了条件一（在满足其他人条件时，这个要求被做了修改），那么就满足条件二。如果条件二也无法满足，则再去尝试条件一。（有可能别人要满足的一个条件和自己要满足的条件互相冲突，但可以自己换另一个条件而保证所有条件成立）
首先建立一个二维数组用来存储每个的要求（因为之后要循环判断多次每个人的条件），和一个数组来存储所有配料加或不加。做一个循环来判断每个人的要求，并作出修改。（要进行多次判断与修改，也就是要循环多次这个循环）最后进行一次判断，若每人的要求都满足了，就正常输出。否则输出“IMPOSSIBLE”
代码实现
#include <bits/stdc++.h>
using namespace std;
int n, m, b[3][100005]; // 记录每个人的愿望要针对的食材
bool s[100005], a[3][100005], d[3][100005];
// s[i]表示每种调料要不要放
// a表示每个愿望针对的食材要不要
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) { // 输入
char c;
cin >> c;
cin >> b[1][i];
if (c == '+') {
a[1][i] = true;
}
cin >> c;
cin >> b[2][i];
if (c == '+') {
a[2][i] = true;
}
}
for (int l = 1; l <= 500; l++)
for (int i = 1; i <= n; i++) {
if (s[b[1][i]] == a[1][i] || s[b[2][i]] == a[2][i]) {
} else {
if (!d[1][i]) { // 修改希望1
s[b[1][i]] = a[1][i];
d[1][i] = true; // 下次会修改希望2
} else if (!d[2][i]) { // 修改希望2
s[b[2][i]] = a[2][i];
// d[2][i]=true;//运行这行并注释下一行会95分
d[1][i] = false; // 下次修改希望1
} else { // 没用
cout << "IMPOSSIBLE";
return 0;
}
}
}
for (int i = 1; i <= n; i++) { // 进行判断
if (s[b[1][i]] == a[1][i] || s[b[2][i]] == a[2][i]) {
} else {
cout << "IMPOSSIBLE";
return 0;
}
}
for (int i = 1; i <= m; i++) {
if (s[i]) {
cout << "+ ";
} else {
cout << "- ";
}
}
return 0;
}
T6 航班请求
题目描述
有n个城市有机场但没有航班连接。给定m个请求，需要能够旅行到每个请求的路线。你的任务是确定使得所有请求成立所需的最小单程航班连接数。
思路解析
要解决这个问题，我们可以将其视为一个图论问题。每个城市可以看作图中的一个节点，而每个请求可以看作图中的一条路径。我们需要找到最小的单程航班连接数，使得所有请求的路径都能被满足。
我们可以使用以下步骤来解决这个问题：
- 构建图：将每个城市作为一个节点，初始时图中没有边。
- 处理请求：对于每个请求，我们需要确定从一个城市到另一个城市的路径。如果这两个城市之间没有直接连接，我们需要添加一条边。
- 最小生成树：为了最小化单程航班连接数，我们可以使用最小生成树的概念。最小生成树可以确保我们用最少的边连接所有节点。
- Kruskal算法：我们可以使用Kruskal算法来找到最小生成树。Kruskal算法的基本思想是按照边的权重（这里可以假设所有边的权重为1）从小到大排序，然后依次选择边，如果这条边的两个节点不在同一个连通分量中，则将这条边加入生成树中。
- 并查集：为了高效地判断两个节点是否在同一个连通分量中，我们可以使用并查集数据结构。
以下是具体的实现步骤：
- 初始化并查集：为每个节点创建一个集合。
- 处理请求：对于每个请求，如果两个城市不在同一个集合中，则将它们合并，并记录这条边。
- 统计边数：最终统计添加的边数，即为所需的最小单程航班连接数。
代码实现
主播没A，就不放了
标签：cnt,每个,int,Day7,void,2024,蓝润,low,节点 From： https://www.cnblogs.com/TangyixiaoQAQ/p/18316753