题解 CF711D 【Directed Roads】
Starlight237
·
·
题解
推结论的过程其他题解都已经阐明，此处不再赘述，仅叙述一下使用 $\text{tarjan}$ 对无向图找环的方法和注意事项。
- 由于在无向图中，任何一个连通的局部都构成强连通分量，故采用普通的 $\text{tarjan}$ 就会出现问题。
- 究其原因，任何两点之间都构成了一个环。因此永远可以沿原路返回。
- 我们可以在 `tarjan` 递归函数中加入一个参数 `Fa` 表示当前是从哪个点过来的，往后走的时候就不能再原路折回。
- 此时求得的即是无向图的环。
注意事项：
1. 由于题目可能有重边，故应当 `sort` 一下，对于重边不计入总边数。
2. 容易知道，一个无自环的图中，任何一个的环的边数都等于点数。故我们可以统计环中的点数。
3. 最后统计环的时候，若 `rt[i] == i && siz[i] > 1`，则构成一个环。其中 `rt[i]` 表示 i 所在强连通分量的代表节点。注意，不可以在 `tarjan` 函数中那个 `if` 语句里面更新答案，因为此时可能找到的并不是最终的环，而是一个非简单环的局部，甚至只有一个点。事实上，如果在 `tarjan` 函数中那个 `if` 语句里面更新答案，则样例 2 会输出 `14`。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define reg register
extern "C" {
namespace io{
#define BUFS 100000
static char in[BUFS], *p = in, *pp = in, out[BUFS << 7], *q = out, ch[20], *t = ch;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
inline int read() {
reg int x = 0; reg char ch, f = 0;
while (!isdigit(ch = gc())) f |= ch == '-';
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return f ? -x : x;
}
inline void write(int x, char sp) {
x || (*q++ = 48), x < 0 && (*q++ = '-', x = -x);
while (x) *t++ = x % 10 + 48, x /= 10;
while (t != ch) *q++ = *--t;
*q++ = sp;
}
inline void flush() {fwrite(out, 1, q - out, stdout);}
}}
#define rd io :: read
#define wt io :: write
const int N = 400001, mod = 1e9 + 7;
int n, m, tot, tim, head[N], dfn[N], vis[N], pw[N], ans = 1, rt[N], siz[N], low[N];
struct Eg{int u, v;}EG[N << 1];
inline bool operator<(const Eg&a, const Eg&b) {return a.u != b.u ? a.u < b.u : a.v < b.v;}
struct Edge{int v, nxt;} eg[N << 1];
inline void addedge(int u, int v) {eg[++tot] = Edge{v, head[u]}, head[u] = tot;}
int stk[N], *tp = stk;
void tarjan(int x, int Fa) {
dfn[x] = low[x] = ++tim, *++tp = x, vis[x] = 1;
for (reg int i = head[x], v; i; i = eg[i].nxt)
(v = eg[i].v) != Fa &&(
!dfn[v] ? tarjan(v, x), low[x] = min(low[x], low[v]) :
(vis[v] && (low[x] = min(low[x], dfn[v])))
);
if (low[x] == dfn[x]) {
reg int y;
do
y = *tp, rt[y] = x, vis[y] = 0, x != y && (siz[x] += siz[y]), --tp;
while (x != y);
}
}
int main() {
n = rd();
pw[0] = 1;
for (reg int i = 1; i <= n; ++i) pw[i] = ((long long)pw[i - 1] << 1)%mod;
for (reg int i = 1, x; i <= n; ++i) x = rd(), EG[i] = Eg{min(i, x), max(i, x)};
sort(EG + 1, EG + n + 1);
for (reg int i = 0; i < n; ++i)
!(EG[i].u == EG[i + 1].u && EG[i].v == EG[i + 1].v) && (addedge(EG[i + 1].u, EG[i + 1].v), addedge(EG[i + 1].v, EG[i + 1].u), ++m, 0);
for (reg int i = 1; i <= n; ++i) siz[i] = 1;
for (reg int i = 1; i <= n; ++i) dfn[i] || (tarjan(i, 0), 0);
for (reg int i = 1; i <= n; ++i)
rt[i] == i && siz[i] > 1 && (ans = (long long)ans * (pw[siz[i]] - 2 + mod) % mod, m -= siz[i]);
ans = (long long)ans * pw[m] % mod;
wt(ans, '\n');
io :: flush();
return 0;
}
```