Graph Algorithms

0FindingKthAncestorInRootedTree.cpp

#include<bits/stdc++.h>
using namespace std;

void dfs(bool visited[], vector<int> adj[], int parent[], int s){
    for(auto u: adj[s]){
        if(visited[u]) continue;
        visited[u]=true;
        parent[u]=s;
        dfs(visited, adj, parent, u);
    }
}

int main(){
    int n; cin>>n;
    vector<int> adj[n+1]; // nodes are 1,2,...,N
    
    // Taking input of n-1 edges.
    for(int i=1; i<n; i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }

    int parent[n+1];
    parent[0]=parent[1]=0;

    bool visited[n+1]; 
    memset(visited, false, sizeof(visited));
    dfs(visited,adj,parent,1); // Tree rooted at 1

    // Taking input the node number and the k to find k-th ancestor.
    int node, k; cin>>node>>k;
    cout<<k<<"-th ancestor of "<<node<<" is: ";
    while(k>0 && node!=0){
        node=parent[node];
        k--;
    }

    cout<<node<<"\n";

    return 0;
}

1input.txt

8   
1 2
1 3
1 4
2 5
2 6
6 8
4 7

2 1

1output.txt

1-th ancestor of 2 is: 1

2input.txt

8
1 2
1 3
1 4
2 5
2 6
6 8
4 7

8 2

2output.txt

2-th ancestor of 8 is: 2

3input.txt

8
1 2
1 3
1 4
2 5
2 6
6 8
4 7

8 4

3output.txt

4-th ancestor of 8 is: 0