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("%dn", ans);
}

Second solution

#include <bits/stdc++.h>
#define MAX 100005
#define INF 1000000009

using 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;
}

coding problems solutions