Advertisement
Josif_tepe

Untitled

Oct 23rd, 2024
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6. vector<int> graph[50001];
  7.  
  8. int main() {
  9.     int n;
  10.     cin >> n;
  11.    
  12.     for(int i = 0; i < n; i++) {
  13.         int x;
  14.         cin >> x;
  15.         x--;
  16.         graph[i].push_back(x);
  17.     }
  18.    
  19.     vector<bool> visited_bfs(n, false);
  20.     int res = 0;
  21.     for(int i = 0; i < n; i++) {
  22.         if(!visited_bfs[i]) {
  23.             queue<int> q;
  24.             q.push(i);
  25.            
  26.             vector<bool> visited(n, false);
  27.             visited[i] = true;
  28.             int nodes = 1;
  29.             while(!q.empty()) {
  30.                 int node = q.front();
  31.                 q.pop();
  32.                
  33.                 for(int j = 0; j < (int) graph[node].size(); j++) {
  34.                     int neighbour = graph[node][j];
  35.                    
  36.                     if(!visited[neighbour]) {
  37.                         visited[neighbour] = true;
  38.                         visited_bfs[neighbour] = true;
  39.                         q.push(neighbour);
  40.                         nodes++;
  41.                         res = max(res, nodes);
  42.                     }
  43.                    
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     cout << res << endl;
  49.    
  50.     return 0;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement