Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4.  
  5.  
  6. vector<vector<ll>>g;
  7. ll n;
  8. void edge(ll a,ll b)
  9. {
  10.     g[a].push_back(b);
  11. }
  12.  
  13. ll count1=0;
  14.  
  15. void dfs_visit(ll v,bool visited[])
  16. {
  17.  
  18.     visited[v]=true;
  19.     //cout << v << " ";
  20.  
  21.  
  22.     for(auto i=g[v].begin();i!=g[v].end();i++)
  23.     {
  24.         if(!visited[*i])
  25.         {
  26.             count1++;
  27.             dfs_visit(*i,visited);
  28.         }
  29.     }
  30.  
  31. }
  32.  
  33. ll dfs(ll v)
  34. {
  35.     bool visited[n+5];
  36.  
  37.     for(int i=1;i<=n;i++)
  38.     {
  39.         visited[i]=false;
  40.     }
  41.     count1=0;
  42.     dfs_visit(v,visited);
  43.     return count1;
  44. }
  45.  
  46. int main()
  47. {
  48.     ll q;
  49.     cin>>q;
  50.     while(q--)
  51.     {
  52.  
  53.         cin>>n;
  54.         g.assign(n+1,vector<ll>());
  55.         ll ara[n+5];
  56.         for(int i=1;i<=n;i++)
  57.         {
  58.             cin>>ara[i];
  59.             edge(i,ara[i]);
  60.         }
  61.  
  62.         for(int i=1;i<=n;i++)
  63.         {
  64.             cout << dfs(i)+1 << " ";
  65.         }
  66.         cout << "\n";
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement