本文共 2188 字，大约阅读时间需要 7 分钟。
#include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ULL; const int MAXN(100010); const int MAXE(100010); template bool checkmin(T &a, const T &b){ return b < a? (a = b, true): false; } template bool checkmax(T &a, const T &b){ return b > a? (a = b, true): false; } inline int lowb(int i){ return i&-i;} int gcd(int a, int b){ while(b){ int t = a%b; a = b; b = t; } return a; } struct E{ int u, v; E *next; }; struct G{ E *h[MAXN]; E e[MAXE], *r; void init(int n){ memset(h, 0, sizeof(h[0])*(n+1)); r = e; } void add(int u, int v){ r->u = u; r->v = v; r->next = h[u]; h[u] = r++; } } g, g1, g2, g3; stack st; int co[MAXN], rep[MAXN], to[MAXN], ind[MAXN], out[MAXN], cn; bool vis[MAXN]; void dfs(int u){ vis[u] = true; for(E *i = g.h[u]; i; i = i->next) if(!vis[i->v]) dfs(i->v); st.push(u); } void dfs1(int u){ co[u] = cn; for(E *i = g1.h[u]; i; i = i->next) if(!co[i->v]) dfs1(i->v); } void dfs2(int u, int rt){ vis[u] = true; bool leaf(true); for(E *i = g2.h[u]; i; i = i->next){ leaf = false; if(!vis[i->v]) dfs2(i->v, rt); } if(leaf) to[u] = rt; } int main(){ int n, u; scanf("%d", &n); g.init(n); g1.init(n); for(int i = 1; i <= n; ++i){ scanf("%d", &u); g.add(i, u); g1.add(u, i); } for(int i = 1; i <= n; ++i) if(!vis[i]) dfs(i); while(!st.empty()){ u = st.top(); st.pop(); if(co[u]) continue; co[u] = ++cn; rep[cn] = u; dfs1(u); } if(cn == 1){ printf("0\n"); return 0; } g2.init(cn); memset(ind, 0, sizeof(ind[0])*(cn+1)); for(E *i = g.e; i < g.r; ++i) if(co[i->u] != co[i->v]){ g2.add(co[i->v], co[i->u]); ++out[co[i->u]]; ++ind[co[i->v]]; } memset(vis, 0, sizeof(vis[0])*(cn+1)); for(int i = 1; i <= cn; ++i) if(out[i] == 0) dfs2(i, i); int ans = 0, f = 0; for(int i = 1; i <= cn; ++i) if(ind[i] == 0){ if(!f) f = i; ++ans; } printf("%d\n", ans); int l = f; for(int i = f+1; i <= cn; ++i) if(ind[i] == 0){ printf("%d %d\n", rep[to[l]], rep[i]); l = i; } printf("%d %d\n", rep[to[l]], rep[f]); return 0; }
转载于:https://www.cnblogs.com/jianrenfang/p/7497921.html