---
# System prepended metadata

title: Leetcode_2876. Count Visited Nodes in a Directed Graph
tags: [Hard, "Leetcode\_"]

---

# Leetcode_2876. Count Visited Nodes in a Directed Graph
###### tags: `Leetcode` `Hard`
There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.

You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].

Consider the following process on the graph:

You start from a node x and keep visiting other nodes through edges until you reach a node that you have already visited before on this same process.
Return an array answer where answer[i] is the number of different nodes that you will visit if you perform the process starting from node i.

![](https://hackmd.io/_uploads/rk_3zd8Z6.png)
![](https://hackmd.io/_uploads/HkMTGdLWT.png)

``` c=
class Solution {
public:
    vector<int> countVisitedNodes(vector<int>& edges) {
       int n=edges.size();
       vector<int>res(n,0);
       for(int i=0,j;i<n;++i){
           j=i;
           unordered_set<int> seen;
           vector<int>s;
            // until find a node that has been fined or a cycle    
           while(!seen.count(j) && res[j]==0){
               seen.insert(j);
               s.push_back(j);
               j=edges[j];
           }
           // cycle
           if(seen.count(j)){
               //  1-> (2->3->4->5->2)  <- cycle 2-5
               int k=distance(find(s.begin(), s.end(), j),s.end());
               for(int i=0;i<k;i++){
                   res[s.back()]=k;
                   s.pop_back();
               }
           }
           // a node that have been fined (cycle node)
           while(!s.empty()){
               j=s.back();
               s.pop_back();
               res[j]=res[edges[j]]+1;
           }
       }
       return res;
    }
};
```
