基環樹森林，然而我比較菜，直接tarjan找環。

發現縮點之后變成了DAG，每一個點往下走一定會走到一個環，縮點之后搜一遍看看會走到哪個環以及那個環的編號是多少，答案就是環的$siz$$ + $要走的路程。

比較垃圾的我忘記了判重邊WA了好多發……

時間復雜度$O(n)$。

Code：

#include <cstdio> #include <cstring> using namespace std;const int N = 1e5 + 5; const int inf = 1 << 30;int n, to[N], dfsc = 0, dfn[N], low[N], cur[N]; int scc = 0, siz[N], top = 0, sta[N], bel[N], dis[N]; int tot = 0, head[N]; bool vis[N], isCur[N];struct Edge {int to, nxt; } e[N];inline void add(int from, int ver) {e[++tot].to = ver;e[tot].nxt = head[from];head[from] = tot; }inline void read(int &X) {X = 0; char ch = 0; int op = 1;for(; ch > '9'|| ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op; }inline int min(int x, int y) {return x > y ? y : x; }inline int max(int x, int y) {return x > y ? x : y; }void tarjan(int x) {dfn[x] = low[x] = ++dfsc;sta[++top] = x, vis[x] = 1;int y = to[x];if(!dfn[y]) {tarjan(y);low[x] = min(low[x], low[y]);} else if(vis[y]) low[x] = min(low[x], dfn[y]);if(low[x] == dfn[x]) {++scc;for(; sta[top + 1] != x; --top) {bel[sta[top]] = scc;siz[scc]++;vis[sta[top]] = 0;}} }void dfs(int x) {vis[x] = 1;if(isCur[x]) {dis[x] = 0, cur[x] = x;return;}for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(!vis[y]) dfs(y);dis[x] = dis[y] + 1, cur[x] = cur[y];} }int main() { // freopen("testdata.in", "r", stdin); // freopen("mine.out", "w", stdout); read(n);for(int i = 1; i <= n; i++) read(to[i]);for(int i = 1; i <= n; i++)if(!dfn[i]) tarjan(i);/* for(int i = 1; i <= n; i++)printf("%d ", bel[i]);printf("\n"); */for(int i = 1; i <= n; i++)if(to[i] == i) isCur[bel[i]] = 1;for(int i = 1; i <= scc; i++) if(siz[i] >= 2) isCur[i] = 1;for(int i = 1; i <= n; i++) {if(bel[i] == bel[to[i]]) continue;add(bel[i], bel[to[i]]);} for(int i = 1; i <= scc; i++)if(!vis[i]) dfs(i);/* for(int i = 1; i <= scc; i++)printf("%d ", cur[i]);printf("\n"); */for(int i = 1; i <= n; i++) {if(isCur[bel[i]]) printf("%d\n", siz[bel[i]]);else printf("%d\n", dis[bel[i]] + siz[cur[bel[i]]]);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/CzxingcHen/p/9595345.html

總結

以上是生活随笔為你收集整理的Luogu 2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。