这题树套环太不容易了 至少连续写了一天
首先一开始对于找环的处理 需要将每次不同点的dfs进行不同vis标记
其次进行逆序dfs找重点的时候只需要判断已开始是不是环就可以了 之后不会有环的
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> #include<queue> #include<set> #include<map> #include<ctime> using namespace std; const int MAXN = 1e5 + 5; int n; int A[MAXN]; int Next[MAXN<<1]; int vis[MAXN<<1]; //dfs判环 之后用于判重 int mean[MAXN<<1]; int indegree[MAXN<<1]; int no[MAXN]; int go[MAXN]; map<int,int> Hash; int target; // dfs时候编号用 int cnt[MAXN<<1]; int tot; vector<int> cc[MAXN]; vector<int> mp[MAXN<<1]; vector<int> ans; void Findloop(int x,int root){ if(x == root) return; mean[x] = target; cc[tot].push_back(x); Findloop(Next[x], root); } void dfs(int x,int tag){ // printf("%d %d\n",x,tag); if(vis[x] != tag && vis[x]!=-1) return; if(vis[x] == tag){ target = x; mean[x] = target; Hash[target] = ++tot; cc[tot].clear(); cc[tot].push_back(x); Findloop(Next[x],x); return; } vis[x] = tag; dfs(Next[x],tag); } void Find(int x,int pre){ for(auto i : mp[x]){ if(i == pre) continue; go[i/2] ++; if(go[i/2] == 2) no[i/2] = 1; Find(i,x); go[i/2] --; } } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); tot = 0; memset(cnt,0,sizeof(cnt)); memset(vis,-1,sizeof(vis)); memset(no,0,sizeof(no)); memset(go,0,sizeof(go)); memset(indegree,0,sizeof(indegree)); ans.clear(); Hash.clear(); for(int i = 0; i < n; ++i){ scanf("%d",&A[i]); } for(int i = 0; i < 2*n; ++i) { mean[i] = i; mp[i].clear(); } for(int i = 0; i < n; ++i){ int t1,t2; if(i%2==0) t1 = (i+A[i]+n)%n*2 , t2 = (i-A[i]+n)%n*2; else t1 = (i+A[i]+n)%n*2+1 , t2 = (i-A[i]+n)%n*2+1; Next[2*i] = t1; Next[2*i+1] = t2; } for(int i = 0; i < n; ++i){ target = -1; dfs(2*i,2*i); target = -1; dfs(2*i+1,2*i+1); } // for(int i = 0 ; i < 2*n; ++i) printf("%d ",mean[i]); printf("\n"); for(int i = 0; i < n; ++i){ int a = mean[2*i]; int b = mean[2*i+1]; int c = mean[Next[2*i]]; int d = mean[Next[2*i+1]]; if(a != c) mp[c].push_back(a), indegree[a] ++; if(d != b) mp[d].push_back(b),indegree[b] ++; }memset(vis,0,sizeof(vis)); for(int i = 0; i < 2*n; ++i){ int tt = mean[i]; if(indegree[tt] == 0 && vis[tt] == 0){ if(Hash[tt]) { for(auto j : cc[ Hash[tt] ]){ vis[j]++; no[j/2] = 1; } }else vis[tt]++, go[tt/2] ++; Find(tt,-1); } } for(int i = 0; i < n; ++i) if(no[i] == 0) ans.push_back(i); printf("%lu\n",ans.size()); for(int i = 0; i < ans.size(); ++i) if(!i) printf("%d",ans[i]); else printf(" %d",ans[i]); printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Basasuya/p/8433769.html