今后需要改良一下拓扑排序，不要一遍一遍扫。只要抓到一个入度为0的就紧追不舍即可，一遍一遍的扫很耗费时间的。。。具体可看代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<iostream> #include<algorithm> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int nxt[100005]; bool visited[100005]; int allocated[100005]; int alloc_ptr = 0; int allocate_dis[100005]; int chainDis[100005]; int inDegree[100005]; inline void removeInDegree(int node) { if (inDegree[node] != 0)return; inDegree[node]--; inDegree[nxt[node]]--; removeInDegree(nxt[node]); } inline int dfsRing(int alloc, int node) { if (visited[node])return 0; visited[node] = true; allocated[node] = alloc; return 1 + dfsRing(alloc, nxt[node]); } inline int dfsToRing(int node) { if (chainDis[node] != 0)return chainDis[node]; if (allocated[node])return chainDis[node] = allocate_dis[allocated[node]]; else return chainDis[node] = 1 + dfsToRing(nxt[node]); } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { cin >> nxt[i]; inDegree[nxt[i]]++; } for (int i = 1; i <= n; i++) { if (inDegree[i] == 0)removeInDegree(i); } for (int i = 1; i <= n; i++) { if (inDegree[i] <= 0 || allocated[i]) continue; alloc_ptr++; allocate_dis[alloc_ptr] = dfsRing(alloc_ptr, i); } for (int i = 1; i <= n; i++) { if (allocated[i])cout << allocate_dis[allocated[i]] << endl; else cout << dfsToRing(i) << endl; } } |