强连通分量+缩点
使用tarjan算法求强连通分量,再把强连通分量缩成一个点。
所需的数据结构
int dfn[10004];//遍历到i节点时的时间戳
int low[10004];//i节点不通过父节点可以回溯到的最小时间戳
int book[10004];//表示i是否入栈
stack<int> s;
先读入点和边
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> power[i];
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
a[x[i]].push_back(y[i]);
}
因为图可能不连通,所以以多个点为根dfs
//dfn数组充当了标记数组
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
dfs(i);
最重要的是dfs函数
将遍历到的每个点都入栈,栈中的节点构成了祖先和儿子的关系
如果一个节点的子节点未访问过,则继续dfs(子节点),且更新low
如果一个节点的子节点访问过且在栈中(在栈中表明这个节点和它的子节点存在祖先和儿子的关系),
该节点可以回溯到祖先节点,更新low
如果一个节点的dfn--low,说明
- 1,该节点无法通过子节点回溯到祖先节点,即不存在环,所以这一个节点为一个强连通分量。将这个节点出栈。
- 2,该节点通过子节点回溯到他自己,表示存在一个以该节点为起始点的环。环上的所有点可以被所称一个点。将栈中的节点出栈直到这个节点出去。
然后重建缩点后的图(有向无环图)
进行接下来的操作。
模板题
P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<map>
using namespace std;
int n, m, power[10004], x[100005], y[100005], t = 1, tot, col[10004], money[10004], ans;
vector<int> a[10004];
int dfn[10004];//遍历到i节点时的时间戳
int low[10004];//i节点不通过父节点可以回溯到的最小时间戳
int book[10004];//表示i是否入栈
stack<int> s;
int ind[10004];
void dfs(int x);
void getans(int x, int p);
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> power[i];
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
a[x[i]].push_back(y[i]);
}
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
dfs(i);
//重新建立缩点后的图
for (int i = 1; i <= n; i++)
a[i].clear();
for (int i = 1; i <= m; i++)
{
if (col[x[i]] != col[y[i]]) //如果两个点不在一个连通分量中,则连边(两个点可能连多条相同的边)
{
a[col[x[i]]].push_back(col[y[i]]);
ind[col[y[i]]]++;
}
}
//dfs求具体的数据
memset(book, 0, sizeof(book));
for (int i = 1; i <= tot; i++)
{
if (ind[i] == 0)
{
book[i] = 1;
getans(i, money[i]);
}
}
cout << ans;
return 0;
}
void dfs(int x)
{
s.push(x);//将x入栈
dfn[x] = t; low[x] = t; t++;//初始化
book[x] = 1;//表明x已经入栈
int len = a[x].size();
for (int i = 0; i < len; i++)
{
if (dfn[a[x][i]] == 0)//如果子节点未被搜索过,继续搜索
{
dfs(a[x][i]);
low[x] = min(low[x], low[a[x][i]]);//x节点如果能通过子节点走到dfn小的祖先,更新
}
if (dfn[a[x][i]] != 0 && book[a[x][i]] == 1)//子节点搜索过,且在栈内
{
low[x] = min(low[x], dfn[a[x][i]]);
}
}
if (dfn[x] == low[x])//x为强连通块的根
{
tot++;//tot为强连通的编号
while (s.top() != x)
{
col[s.top()] = tot;
book[s.top()] = 0;
money[tot] += power[s.top()];
s.pop();
}
col[s.top()] = tot;
book[s.top()] = 0;
money[tot] += power[s.top()];
s.pop();
}
}
void getans(int x, int p)
{
ans = max(ans, p);
int len = a[x].size();
for (int i = 0; i < len; i++)
{
if (book[a[x][i]] == 0)
{
book[a[x][i]] = 1;
getans(a[x][i], p + money[a[x][i]]);
book[a[x][i]] = 0;
}
}
}