# HackerEarth GCD on directed graph problem solution

In this HackerEarth GCD on directed graph problem solution You are given a directed graph with n nodes and m edges. The nodes are numbered from 1 to n, and node i is assigned a cost ci. The cost of a walk on the graph is defined as the greatest common divisor of the costs of the vertices used in the walk. Formally, the cost of a walk v1,v2,...,vk is given by gcd(cv1,cv2,...,cvk). Note that vi's need not be distinct. Find the cost of the walk with minimum cost.

The walk might consist of single vertex.

## HackerEarth GCD on directed graph problem solution.

`#include <bits/stdc++.h>using namespace std;#define fst first#define snd second#define all(c) ((c).begin()), ((c).end())const int N = 1e5 + 10;vector<int> divs[N];struct graph {  int n;  vector<vector<int>> adj;  vector<int> val;  vector<int> I;  graph(int n) : n(n), adj(n), val(n), I(n) { }  void add_edge(int src, int dst) {    adj[src].push_back(dst);  }  vector<vector<int>> strongly_connected_components() {    vector<vector<int>> scc;    vector<int> S, B;    function<void(int)> dfs = [&](int u) {      B.push_back(I[u] = S.size());      S.push_back(u);      for (int v: adj[u]) {        if (!I[v]) dfs(v);        else while (I[v] < B.back()) B.pop_back();      }      if (I[u] == B.back()) {        scc.push_back({});        B.pop_back();        for (; I[u] < S.size(); S.pop_back()) {          scc.back().push_back(S.back());          I[S.back()] = n + scc.size();        }      }    };    for (int u = 0; u < n; ++u)      if (!I[u]) dfs(u);    for(int i = 0; i < n; i++) I[i] -= n + 1;    return scc; // I[u] - n is the index of u  }  graph scc_dag(){    vector<vector<int> > vec = strongly_connected_components();    graph ret(vec.size());    for(int i = 0; i < n; i++){      ret.val[I[i]] = __gcd(ret.val[I[i]], val[i]);      for(int j : adj[i]){        if(I[i] != I[j]) ret.add_edge(I[i], I[j]);      }    }    return ret;  }};void pre(){  for(int i = 0; i < N; i++) divs[i].reserve(10);  for(int i = 1; i < N; i++){    for(int j = i; j < N; j += i) divs[j].push_back(i);  }}unordered_set<int> dp[N];vector<int> con[N];int main(){  pre();  int n, m, u, v;  scanf("%d %d", &n, &m);  graph G(n);  for(int i = 0; i < n; i++) scanf("%d", &G.val[i]);  for(int i = 0; i < m; i++){    scanf("%d %d", &u, &v);    u--; v--;    G.add_edge(u, v);  }  graph g = G.scc_dag();  n = g.n;  for(int i = 0; i < n; i++){    for(int j : g.adj[i]) con[j].push_back(i);  }  int ans = g.val[n - 1];  dp[n - 1].insert(g.val[n - 1]);  for(int i = n - 2; i >= 0; i--){    dp[i].insert(g.val[i]);    ans = min(ans, g.val[i]);    for(int j : con[i])      for(int d : dp[j]){        int r = __gcd(d, g.val[i]);        dp[i].insert(r);        ans = min(ans, r);      }  }  cerr << "time taken = " << clock() / (double) CLOCKS_PER_SEC << endl;  cerr << "answer = " << ans << endl;  printf("%d\n", ans);}`

### Second solution

`#include <bits/stdc++.h>#define MAX 100005#define INF 1000000009using namespace std;int A[MAX];int val[MAX];vector <int> v[MAX];vector <int> rev_v[MAX];vector <int> scc_v[MAX];vector < pair <int, int> > edges;bool vis[MAX];int comp[MAX];stack <int> s;int components;set <int> ss[MAX];void dfs_0(int curr){    vis[curr] = true;    for ( int i = 0; i < (int)v[curr].size(); i++ ) {        if ( vis[v[curr][i]] ) continue;        dfs_0(v[curr][i]);    }    s.push(curr);    }void dfs_1(int curr){    vis[curr] = true;    comp[curr] = components;    val[components] = __gcd(val[components], A[curr]);    for ( int i = 0; i < (int)rev_v[curr].size(); i++ ) {        if ( vis[rev_v[curr][i]] ) continue;         dfs_1(rev_v[curr][i]);    }}void dfs_2(int curr){    vis[curr] = true;    for ( int i = 0; i < (int)scc_v[curr].size(); i++ ) {        if ( vis[scc_v[curr][i]] ) continue;        dfs_2(scc_v[curr][i]);    }    s.push(curr);}int main(){    int n, m, x, y;        cin >> n >> m;    assert(n >= 1 && n <= 100000);    assert(m >= 1 && m <= 100000);        for ( int i = 1; i <= n; i++ ) {        cin >> A[i];        assert(A[i] >= 1 && A[i] <= 100000);    }    for ( int i = 0; i < m; i++ ) {        cin >> x >> y;        assert(x >= 1 && x <= n);        assert(y >= 1 && y <= n);        edges.push_back(make_pair(x, y));        v[x].push_back(y);        rev_v[y].push_back(x);    }        for ( int i = 1; i <= n; i++ ) {        if ( !vis[i] ) dfs_0(i);    }        memset(vis, false, sizeof(vis));        components = 0;        while ( !s.empty() ) {        int curr = s.top();        s.pop();        if ( !vis[curr] ) {            components++;            dfs_1(curr);        }    }        //Create an scc condensed dag graph    //Number of vertices = components    //Edges -> scc[]    //Value on each node of this scc - val[i]    for ( int i = 0; i < m; i++ ) {        if ( comp[edges[i].first] != comp[edges[i].second] ) {            scc_v[comp[edges[i].first]].push_back(comp[edges[i].second]);        }            }        memset(vis, false, sizeof(vis));        //Perform a topological sort on this.        for ( int i = 1; i <= components; i++ ) {        if ( !vis[i] ) dfs_2(i);    }        int ans = INF;        while ( !s.empty() ) {        int curr = s.top();        s.pop();        ss[curr].insert(val[curr]);        ans = min(ans, val[curr]);        for ( set <int> :: iterator it = ss[curr].begin(); it != ss[curr].end(); it++ ) {            for ( int j = 0; j < (int)scc_v[curr].size(); j++ ) {                ss[scc_v[curr][j]].insert(__gcd(*it, val[scc_v[curr][j]]));                ans = min(ans, __gcd(*it, val[scc_v[curr][j]]));            }        }    }        cout << ans << endl;        return 0;}`