#include <bits/stdc++.h>
using namespace std;
// 存图
const int MAXN = 100000;
const int MAXM = 200000;
int n, m;
// 存图
vector<int> e[MAXN + 5];
// 每个点的入度/出度
int inD[MAXN + 5], outD[MAXN + 5];
// 欧拉路的起点终点
int st, ed;
// 每个点已经搞定了几条边
int cnt[MAXN + 5];
// 每条边还在不在
bool vis[MAXM + 5];
// 最终路径
stack<int> ans;
void dfs(int u)
{
while (cnt[u] < e[u].size())
{
int v = e[u][cnt[u]];
cnt[u]++;
dfs(v);
}
ans.push(u);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 输入
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
// 计算入度出度
outD[u]++;
inD[v]++;
}
// 如果题目未保证弱连通,那么需要先判断一下
// 找欧拉路的起点终点
int cntD = 0; // 出度入度不相等的点的数量
bool flag = false; // 是否存在出入度相差大于1的点
st = ed = 0;
for (int i = 1; i <= n; i++)
{
if (inD[i] != outD[i])
{
cntD++;
if (abs(inD[i] - outD[i]) > 1)
flag = true;
if (inD[i] + 1 == outD[i])
st = i;
if (outD[i] + 1 == inD[i])
ed = i;
}
}
// 判断是否存在欧拉路
if ((cntD != 2 && cntD != 0) ||
flag ||
(cntD == 2 && (!st || !ed)))
{
cout << "No\n";
return 0;
}
if (cntD == 0)
st = ed = 1;
// 题目要求按字典序最小的欧拉路,排个序
for (int i = 1; i <= n; i++)
sort(e[i].begin(), e[i].end());
dfs(st);
while (!ans.empty())
{
cout << ans.top() << " ";
ans.pop();
}
cout << "\n";
return 0;
}
P2731 [USACO3.3]骑马修栅栏 Riding the Fences
#include <bits/stdc++.h>
using namespace std;
// 存图
const int MAXN = 500;
const int MAXM = 2048;
int n, m;
// pair 为 <边的终点,边的编号>
vector<pair<int, int>> e[MAXN + 5];
// 每个点的度
int d[MAXN + 5];
// 欧拉路的起点终点
int st, ed;
// 每条边还在不在
bool vis[MAXM + 5];
// 最终路径
stack<int> ans;
void dfs(int u)
{
for (int i = 0; i < e[u].size(); i++)
{
int v = e[u][i].first;
int eId = e[u][i].second;
if (vis[eId])
continue;
if (eId <= m)
{
vis[eId] = true;
vis[eId + m] = true;
}
else
{
vis[eId] = true;
vis[eId - m] = true;
}
dfs(v);
}
ans.push(u);
}
bool pFlag[MAXN + 5];
vector<int> points;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 输入
cin >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
pFlag[u] = pFlag[v] = true;
e[u].push_back(make_pair(v, i));
e[v].push_back(make_pair(u, i + m));
// 计算入度出度
d[u]++;
d[v]++;
}
for (int i = 1; i <= MAXN; i++)
if (pFlag[i])
points.push_back(i);
// 如果题目未保证弱连通,那么需要先判断一下
// 找欧拉路的起点终点
st = ed = 0;
for (int i : points)
{
if (d[i] % 2 != 0)
{
if (st == 0)
st = i;
else if (ed == 0)
ed = i;
else
{
cout << "No\n";
return 0;
}
}
}
if (st != 0 && ed == 0)
{
cout << "No\n";
return 0;
}
if (st == 0 && ed == 0)
st = ed = points[0];
if (st > ed)
swap(st, ed);
// 题目要求按字典序最小的欧拉路,排个序
for (int i : points)
sort(e[i].begin(), e[i].end());
dfs(st);
while (!ans.empty())
{
cout << ans.top() << "\n";
ans.pop();
}
cout << "\n";
return 0;
}
对于 dfs 生成树上的点 ,如果他的子节点存在至少一个 ,不走回头路(只靠子节点和返祖边)走不到 的上面。那么 就是割点。
定义:
那么上面的说法可以写成:如果 存在一个子节点 使得 ,那么 就是割点。
以上成立的条件是因为 的父节点方向还有其他点。所以以上对于根节点不适用,根节点是否为割点的判断会更简单。如果无向图 dfs 生成树的根节点有多个子树(超过一个子节点),那么根节点就是割点。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
vector<int> edge[MAXN + 5]; // edge[i]:与i相连的点
bool vis[MAXN + 5], flag[MAXN + 5]; // vis[i]: i有没有走过;flag[i]:i是否为割点
int low[MAXN + 5]; // low[i]:不经过父节点能走到的最小时间戳;
int dfn[MAXN]; // dfn[i]:深搜生成树的时间戳
int idx, resCnt; // idx:时间戳; resCnt:割点数量
void dfs(int u, int fa)
{
vis[u] = true;
low[u] = dfn[u] = ++idx;
int childCnt = 0;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i]; // u->v;
if (!vis[v])
{
childCnt++;
dfs(v, u);
low[u] = min(low[u], low[v]);
if (u != fa && low[v] >= dfn[u] && !flag[u])
{
resCnt++;
flag[u] = true;
}
}
else
{
//正常来说这里必须要求不能走回头路,但是这题无所谓
low[u] = min(low[u], dfn[v]);
}
}
if (u == fa && childCnt >= 2 && !flag[u])
{
resCnt++;
flag[u] = true;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
idx = 0;
dfs(i, i);
}
}
cout << resCnt << endl;
for (int i = 1; i <= n; i++)
if (flag[i])
cout << i << " ";
return 0;
}
对于 dfs 树上的点 ,如果他的子节点 ,不走回头路(只靠子节点和返祖边)甚至走不到 的上面。那么 就是桥。
定义:
那么上面的说法可以写成:如果 存在一个子节点 使得 ,那么 就是桥。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150;
int n, m;
vector<int> edge[MAXN + 5]; // edge[i]:与i相连的点
bool vis[MAXN + 5]; // vis[i]: i有没有走过;
int fa[MAXN + 5]; // fa[i]:i 的父节点
bool flag[MAXN + 5]; // flag[i]:fa[i]~i 是否为桥
int low[MAXN + 5]; // low[i]:不经过父节点能走到的最小时间戳;
int dfn[MAXN]; // dfn[i]:深搜生成树的时间戳
int idx, resCnt; // idx:时间戳; resCnt:割点数量
vector<pair<int, int>> ans;
void dfs(int u, int father)
{
vis[u] = true;
low[u] = dfn[u] = ++idx;
fa[u] = father;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i]; // u->v;
if (!vis[v])
{
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
{
ans.push_back(make_pair(min(u, v), max(u, v)));
flag[v] = true;
}
}
else if (v != father)
{
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
idx = 0;
dfs(i, i);
}
}
sort(ans.begin(), ans.end());
for (auto x : ans)
cout << x.first << " " << x.second << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 2000000;
int n, m;
//<终点坐标,边的编号>
vector<pair<int, int>> edge[MAXN + 5]; // edge[i]:与i相连的所有边
bool visE[MAXM + 5]; // 每条边是否做过了
bool vis[MAXN + 5]; // vis[i]: i有没有走过
int low[MAXN + 5]; // low[i]:不经过父节点能走到的最小时间戳;
int dfn[MAXN]; // dfn[i]:深搜生成树的时间戳
int idx; // idx:时间戳
stack<int> tempS;
int v_bcc_cnt; // 点双数量
vector<int> v_bcc[MAXN + 5]; // 存所有点双
void dfs(int u, int eId)
{
tempS.push(u);
vis[u] = visE[eId] = true;
low[u] = dfn[u] = ++idx;
int childCnt = 0;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first; // u->v;
int uvId = edge[u][i].second;
if (!vis[v])
{
childCnt++;
dfs(v, uvId);
low[u] = min(low[u], low[v]);
// 根节点可以一起做,不管是不是割点,根节点都可以加入下面的点双
if (low[v] >= dfn[u])
{
v_bcc_cnt++;
while (tempS.top() != v)
{
v_bcc[v_bcc_cnt].push_back(tempS.top());
tempS.pop();
}
v_bcc[v_bcc_cnt].push_back(tempS.top());
tempS.pop();
v_bcc[v_bcc_cnt].push_back(u);
}
}
else if (!visE[uvId])
{
low[u] = min(low[u], dfn[v]);
}
}
if (eId == 0 && childCnt == 0)
v_bcc[++v_bcc_cnt].push_back(u);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(make_pair(v, i));
edge[v].push_back(make_pair(u, i));
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
idx = 0;
dfs(i, 0);
}
}
cout << v_bcc_cnt << endl;
for (int i = 1; i <= v_bcc_cnt; i++)
{
cout << v_bcc[i].size() << " ";
for (auto x : v_bcc[i])
cout << x << " ";
cout << endl;
}
return 0;
}
去掉所有的桥,剩下的都是边双。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 2000000;
int n, m;
//<终点坐标,边的编号>
vector<pair<int, int>> edge[MAXN + 5]; // edge[i]:与i相连的边
bool visE[MAXM + 5]; // 每条边是否做过了
bool vis[MAXN + 5]; // vis[i]: i有没有走过;
bool flag[MAXN + 5]; // flag[i]:fa[i]~i 是否为桥
int low[MAXN + 5]; // low[i]:不经过父节点能走到的最小时间戳;
int dfn[MAXN]; // dfn[i]:深搜生成树的时间戳
int idx, resCnt; // idx:时间戳; resCnt:割点数量
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
if (x == fa[x])
return x;
return fa[x] = findFa(fa[x]);
}
void merge(int x, int y)
{
cout << endl;
int faX = findFa(x);
int faY = findFa(y);
if (faX != faY)
fa[faX] = faY;
}
// 存所有边双
vector<int> e_bcc[MAXN + 5];
void dfs(int u, int eId)
{
vis[u] = true;
visE[eId] = true;
low[u] = dfn[u] = ++idx;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first; // u->v;
int uvId = edge[u][i].second; // u->v;
if (!vis[v])
{
dfs(v, uvId);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
{
// u->v 是桥
// cout << u << "x" << v << endl;
}
else
{
merge(u, v);
// cout << u << "~" << v << endl;
}
}
else if (!visE[uvId])
{
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(make_pair(v, i));
edge[v].push_back(make_pair(u, i));
}
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
idx = 0;
dfs(i, 0);
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int faI = findFa(i);
if (e_bcc[faI].empty())
cnt++;
e_bcc[faI].push_back(i);
}
cout << cnt << "\n";
for (int i = 1; i <= n; i++)
{
if (!e_bcc[i].empty())
{
cout << e_bcc[i].size() << " ";
for (int x : e_bcc[i])
cout << x << " ";
cout << "\n";
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
//原图
int n, m;
int a[MAXN + 5]; //点权
vector<int> e[MAXN + 5]; //存图
//tarjan
int idx, dfn[MAXN + 5], low[MAXN + 5];
stack<int> s;
bool inS[MAXN + 5]; //每个点是否在栈中
//存SCC
int sccCnt;
vector<int> scc[MAXN + 5];
//新图(复用 a[] 存新图的每个点权值)
int id[MAXN + 5]; //缩到了新图的哪个点上
vector<int> ee[MAXN + 5]; //新图存边
void dfs(int u)
{
dfn[u] = low[u] = ++idx;
s.push(u);
inS[u] = true;
for (int v : e[u])
{
if(dfn[v] == 0)
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(inS[v])
{
low[u] = min(low[u], dfn[v]);
}
}
//当前点是某个 scc 的根
if(dfn[u] == low[u])
{
++sccCnt;
while(s.top() != u)
{
id[s.top()] = u, a[u] += a[s.top()]; // 缩点
inS[s.top()] = false;
scc[sccCnt].push_back(s.top());
s.pop();
}
//处理 u
id[s.top()] = u; // 缩点
inS[s.top()] = false;
scc[sccCnt].push_back(s.top());
s.pop();
}
}
//拓扑排序、DAG 上 DP
int f[MAXN + 5]; //走到每个点的最大权值之和
int d[MAXN + 5]; //新图的每个点入度
queue<int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//输入
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;
e[u].push_back(v);
}
//缩点
for(int i = 1; i <= n; i++)
if(dfn[i] == 0)
dfs(i);
/*
cout << sccCnt << "\n";
for(int i = 1; i <= sccCnt; i++)
{
cout << scc[i].size() << ":";
for(int x : scc[i])
cout << x << " ";
cout << "\n";
}
for(int i=1;i<=n;i++)
cout << id[i] << ",\n"[i==n];
*/
//建新图
for(int u = 1; u <= n; u++)
for(int v : e[u])
if(id[u] != id[v])
{
ee[id[u]].push_back(id[v]);
d[id[v]]++;
// cout << id[u] << "~" << id[v] << "\n";
}
for(int i = 1; i <= n; i++)
if(d[i] == 0)
{
q.push(i);
f[i] = a[i];
}
int ans = -1;
while(!q.empty())
{
int u = q.front();
q.pop();
ans = max(ans, f[u]);
for(int v : ee[u]){
f[v] = max(f[v], f[u] + a[v]);
d[v]--;
if(d[v] == 0)
q.push(v);
}
}
cout << ans << "\n";
return 0;
}
/*
10 20
986 587 671 143 521 985 204 36 921 990
4 2
2 8
7 8
2 4
1 7
8 7
10 2
5 9
4 5
5 8
4 9
2 7
5 6
9 1
9 6
4 10
9 7
9 2
1 2
5 7
====
5133
*/