Union Find implementation
Consider an iterative path compression design for root. The recursive version uses more memory for stack frames. Typical iterative versions follow the path one at a time. The path can be followed two at a time since the end loops back to itself. The root function could be refactored to be something along the lines of:

int root(int a, vector&lt;int&gt; &amp;parent) {
    while (parent[a] != a)
      a = parent[a] = parent[parent[a]];
    return a;
}


Plus, consider adding a second vector to keep track of the sizes of each group. This will allow for more intelligent selecting of representatives during link. Something along the lines of the following:

void link(int i, int j, vector&lt;int&gt; &amp;parent, vector&lt;int&gt; &amp;sizes) {
  i = root(i, parent);
  j = root(j, parent);
  if (i == j) return;
  if (sizes[i] &lt; sizes[j]) {
    parent[i] = parent[j];
    sizes[j] += sizes[i];
  } else {
    parent[j] = parent[i];
    sizes[i] += sizes[j];
  }
}


See this post for more information.

Consider allocating the vector using the constructor, resize, or reserve. Then initial values can be set using iota (ref).  For example,

vector&lt;int&gt; parent(n);
iota(begin(parent), end(parent), 0);


Consider using printf and scanf over cin and cout. Also, if you are going to use cin and cout, consider including ios_base::sync_with_stdio(false); and cin.tie(NULL);. See this question for more information.