Description

Submission

class Solution {
    vector<vector<int>> graph;
    int ret;
    int k;
    int n;

    void dfs(int cur, int t) {
        if(t == k) {
            if(n - 1 == cur) ++ret;
            return;
        }
        
        for(auto x: graph[cur]) {
            dfs(x, t + 1);
        }
    }
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
        graph.resize(n);
        ret = 0;
        this->k = k;
        this->n = n;

        for(auto& r: relation) {
            graph[r[0]].push_back(r[1]);
        }
        
        dfs(0, 0);

        return ret;
    }
};