本文共 1701 字，大约阅读时间需要 5 分钟。

解题思路：思维性的搜索。搜索时给点标记3，如果还搜到了3，那么就说明构成了一个环，给环标记上2。搜索时如果遇到一个环，那么也说明可以构建一个环，继续返回2，如果没有搜索到环，那么就给标记上1.

#include
   
    using namespace std;typedef long long ll;typedef long double lf;typedef unsigned long long ull;typedef pair
    
     P;const int inf = 0x7f7f7f7f;const ll INF = 1e16;const int N = 1e6+10;const ull base = 131;const ll mod =  1e9+7;const double PI = acos(-1.0);const double eps = 1e-4;inline int read(){   int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){   x=x*10+ch-'0';ch=getchar();}return x*f;}inline string readstring(){   string str;char s=getchar();while(s==' '||s=='\n'||s=='\r'){   s=getchar();}while(s!=' '&&s!='\n'&&s!='\r'){   str+=s;s=getchar();}return str;}int random(int n){   return (int)(rand()*rand())%n;}void writestring(string s){   int n = s.size();for(int i = 0;i < n;i++){   printf("%c",s[i]);}}int a[N],vis[N];int n;int dfs(int i){       if(i < 1 || i > n) return 0;    if(vis[i]==1) return 0;    if(vis[i] == 3 || vis[i] == 2) return 2;    vis[i] = 3;    i = i+a[i];    if(dfs(i)){           vis[i] = 2;        return 2;    }else {           if(i<1||i>n) return 0;        vis[i] = 1;        return 0;    }}void solve(){       n = read();    for(int i = 1;i <= n;i++){           a[i] = read();vis[i] = 0;    }    for(int i = 1;i <= n;i++){           if(dfs(i)){               vis[i] = 2;        }else {               vis[i] = 1;        }    }    int ans = 0;    for(int i = 1;i <= n;i++){           if(vis[i] == 2) ans++;    }    printf("%d\n",ans);}int main(){       //freopen("out.txt","w",stdout);    //srand((unsigned)time(NULL));    int t = read();    while(t--){           solve();    }    return 0;}
    
   

转载地址：http://pkqp.baihongyu.com/