求n减去在环上的元素个数
#include <stdio.h>#include <string.h>#include <vector>#include <stack>#include <algorithm>using namespace std;#define N 111111stack<int>sta;vector<int>mp[N];int dfn[N];int low[N];int InStack[N];int indexx,number;int n, m;int num[N];void tarjan(int u){InStack[u] = 1;low[u] = dfn[u] = ++ indexx;sta.push(u);for (int i = 0; i < mp[u].size(); ++ i){int t = mp[u][i];if (dfn[t] == 0)//如果没有入过栈内，{tarjan(t);//把他遍历一边low[u] = min(low[u], low[t]);//遍历完之后寻找他的子节点中low最小的}else if (InStack[t] == 1)//如果他的某个节点在栈中，，{low[u] = min(low[u], dfn[t]);//最早的时间戳就是他的所有子节点的最早时间}}if (low[u] == dfn[u])//如果找到这两个时间戳相等，那么这个点是此联通图的开始那个点，退栈到u=v{++ number;//表示有几个强连通图while (!sta.empty()){int v = sta.top();sta.pop();InStack[v] = 0;//把它标记为未在栈内num[number]++;if (v == u)break;}}}int main(){int t;int i,n,a;scanf("%d",&t);while(t–){int ans=0;scanf("%d",&n);for(int i=1; i<=n; i++){mp[i].clear();}for(i=1; i<=n; i++){scanf("%d",&a);mp[i].push_back(a);if(i==a) ans++;}memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(InStack, 0, sizeof(InStack));memset(num, 0, sizeof(num));indexx = number = 0;for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);for(i=1; i<=number; i++){if(num[i]>1) ans+=num[i];}printf("%d\n",n-ans);}return 0;}
听过许多故事，见过旅行风景，就这样，
