圆方树
longdie
2020-09-17 17:51:06
# 圆方树
## 学习链接 ： [圆方树](https://www.cnblogs.com/PinkRabbit/p/10446473.html)
## 易错点
1. 理解概念， 圆方树是把每个点双新建成了方点，原来的点是圆点。
2. 理解判定条件 `low[v] == dfn[u]`
3. 注意公共点不出栈
4. 注意每次tarjan后把栈顶减去。
``` cpp
int n, m, cnt, fa[N<<1], ans[N], tot;
vector<int> g[N<<1], t[N<<1];
int dfn[N], low[N], dfs_clock, sta[N], top;
void tarjan(int u) {
low[u] = dfn[u] = ++dfs_clock;
sta[++top] = u;
for(register int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]) {
++cnt;
for(int x = 0; x != v; --top) {
x = sta[top];
t[cnt].push_back(x);
t[x].push_back(cnt);
}
t[cnt].push_back(u);
t[u].push_back(cnt);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
```
## 学习心得
* 方点直接在原来的基础上建即可。
* 一定要注意千万不要把割点出栈。
下面给份代码 ：
``` cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m;
struct edge { int to, next, w; } e[M];
int head[N], cnt;
void add(int x, int y, int z) {
e[++cnt].to = y, e[cnt].next = head[x], e[cnt].w = z, head[x] = cnt;
}
int dfn[N], low[N], dfs_clock, sta[N], top;
void tarjan(int u) {
dfn[u] = low[u] = ++dfs_clock, sta[++top] = u;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]) {
++n; int x = sta[top];
while(x != u) {
add(x, n, 0), add(n, x, 0);
x = sta[--top];
}
add(u, n, 0), add(n, u, 0);// 别忘了加点
}
}
else low[u] = min(low[u], dfn[v]);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int x, y, z; cin >> x >> y >> z;
add(x, y, z), add(y, x, z);
}
for(int i = 1; i <= n; ++i) if(dfn[i]) tarjan(i);
return 0;
}
```
## 圆方树的应用
已经学完了知识，该来道例题了。
#### 题目链接 ： [[ZJOI2004]嗅探器](https://www.luogu.com.cn/problem/P5058)
#### 题解链接 ： [嗅探器](https://www.luogu.com.cn/blog/nitubenben/p5058-zjoi2004-xiu-tan-qi-yuan-fang-shu-ti-xie#)
这篇题解已经讲的很清晰了，不过还有几个注重点，首先需要思考什么时候可以取答案,为什么可以这样就是对的，而不是一味平感觉，只看结论。
下面奉上我自己觉的很好的码风，~~既不那么压行，有简单易懂。~~
``` cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5, M = 2e6 + 5;
int n, nn; int head[N], cnt; int start, target;
struct edge { int to, next; } e[M];
void add(int x, int y) { e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt; }
int dfn[N], low[N], sta[N], top, dfs_clock;
vector<int> g[N];
void tarjan(int u) {
dfn[u] = low[u] = ++dfs_clock, sta[++top] = u;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v); low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]) {
nn++;
while(1) {
int x = sta[top--];
g[x].push_back(nn), g[nn].push_back(x);
if(x == v) break;
} g[u].push_back(nn), g[nn].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u, int fa, int ans) {
if(u == target) {
if(ans == 0) cout << "No solution";
else cout << ans;
exit(0);
}
if(u != start && u <= n && g[u].size() > 1) ans = ans == 0 ? u : min(ans, u);
for(int i = 0; i < g[u].size(); ++i) {
int v = g[u][i]; if(v == fa) continue; dfs(v, u, ans);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n; int x, y; nn = n;
while(cin >> x >> y && x != 0 && y != 0) add(x, y), add(y, x);
cin >> start >> target;
tarjan(start);
if(dfn[target] == 0) return cout << "No solution", 0;
dfs(start, 0, 0);
return 0;
}
```