[UVa] 12533 – Joining Couples

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12533 – Joining Couples
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : LCA, Minimum Spanning Tree, Kruskal Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define pii           pair <int, int>
#define ff            first
#define ss            second
 
static const int maxn = 1e5 + 5;
static const int logn = 18;
 
struct node
{
      int u, v, id;
      node(int u = 0, int v = 0, int id = 0) : u(u), v(v), id(id) {}
      inline bool operator < (const node &p) const
      {
            return id < p.id;
      }
};
 
vector <node> graph;
set <pii> myset, unused;
int parent[maxn];
int father[maxn][logn], depth[maxn];
int whichCompo[maxn];
 
vector <int> tree[maxn];
 
inline void makeSet()
{
      for (int i = 1; i < maxn; i++) parent[i] = i;
}
 
inline int findRep(int r)
{
      if (r == parent[r]) return r;
      return parent[r] = findRep(parent[r]);
}
 
inline void kruskal()
{
      sort(graph.begin(), graph.end());
      makeSet();
      for (node e : graph)
      {
            int p = findRep(e.u);
            int q = findRep(e.v);
            if (p != q)
            {
                  parent[q] = p;
                  tree[e.u].emplace_back(e.v);
                  tree[e.v].emplace_back(e.u);
            }
            else
            {
                  unused.emplace(e.u, e.v);
            }
      }
}
 
inline void dfs(int u, int p, int compo)
{
      for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
      whichCompo[u] = compo;
      for (int v : tree[u])
      {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            father[v][0] = u;
            dfs(v, u, compo);
      }
}
 
inline int LCA(int u, int v) // u and v must be in same tree
{
      if (depth[u] < depth[v]) swap(u, v);
      for (int i = logn-1; i >= 0; i--)
      {
            if (depth[ father[u][i] ] >= depth[v])
            {
                  u = father[u][i];
            }
      }
      if (u == v) return u;
      for (int i = logn-1; i >= 0; i--)
      {
            if (father[u][i] != father[v][i])
            {
                  u = father[u][i];
                  v = father[v][i];
            }
      }
      return father[u][0];
}
 
inline int dist(int u, int v)
{
      int lca = LCA(u, v);
      return depth[u] + depth[v] - 2*depth[lca];
}
 
inline void clean()
{
      graph.clear();
      myset.clear();
      unused.clear();
      for (int i = 0; i < maxn; i++)
      {
            tree[i].clear();
            whichCompo[i] = 0;
            depth[i] = 0;
            for (int j = 0; j < logn; j++) father[i][j] = 0;
      }
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tnode;
      while (cin >> tnode)
      {
            clean();
            int id = 0;
            for (int e = 1; e <= tnode; e++)
            {
                  int f;
                  cin >> f;
                  int u = e;
                  int v = f;
                  if (u > v) swap(u, v);
                  if (u == v) continue;
                  if (myset.find(pii(u, v)) == myset.end())
                  {
                        graph.emplace_back(u, v, ++id);
                        myset.emplace(u, v);
                  }
            }
            kruskal();
            int compo = 0;
            for (int i = 1; i <= tnode; i++)
            {
                  if (depth[i] == 0)
                  {
                        depth[i] = 1;
                        dfs(i, -1, ++compo);
                  }
            }
            int tquery;
            cin >> tquery;
            while (tquery--)
            {
                  int u, v;
                  cin >> u >> v;
                  if (u == v)
                  {
                        cout << "0\n";
                        continue;
                  }
                  if (whichCompo[u] != whichCompo[v])
                  {
                        cout << "-1\n";
                        continue;
                  }
                  int mini = dist(u, v);
                  for (pii p : unused)
                  {
                        if (whichCompo[p.ff] == whichCompo[u] && whichCompo[p.ss] == whichCompo[u])
                        {
                              int case1 = dist(u, p.ff) + 1 + dist(v, p.ss);
                              int case2 = dist(u, p.ss) + 1 + dist(v, p.ff);
                              if (case1 < mini) mini = case1;
                              if (case2 < mini) mini = case2;
                        }
                  }
                  cout << mini << "\n";
            }
      }
}

Another Problem : K. Another Shortest Path Problem