A fair competition

In competition, $N$ participants are competing against each other for the top two spots. There are $M$ friendly relations between participants. In each friendship relation, you will be given two integers $L$ and $R$, indicating $L$ and $R$ are friends.

Note

• If A and B are friends, B and C are friends, then A, B, C will have the same friend circle.
• Two combinations are considered different if either first or second ranker is different.
• The same friendship relation can occur multiple times in input, however, $L$ will never be equal to $R$.

Now, the jury has to decide the winners for the top two spots but he does not want to select both participants from the same friend circle so the competition seems fairer. Find the number of ways in which he can do so.

Example:

Input: n=3, m=1, x=1, y=3
Output: 4

Approach

Java

import java.util.HashMap;
import java.util.Map;

public class FairCompetition {
    public static void main(String args[]) {
        int n = 3;
        int m = 1;
        for (int i = 1; i <= n; i++) {
            makeSet(i);
        }
        int x = 1;
        int y = 3;
        union(x, y);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int p = findSet(i);
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        long ans = 0;
        for (Integer it : map.keySet()) {
            int x1 = map.get(it);
            ans += x1 * 1l * (n - x1);
        }
        System.out.println(ans);
    }

    static private Map<Integer, Node> map = new HashMap<>();

    static class Node {
        int data;
        Node parent;
        int rank;
    }

    static public void makeSet(int data) {
        Node node = new Node();
        node.data = data;
        node.parent = node;
        node.rank = 0;
        map.put(data, node);
    }

    public static boolean union(int data1, int data2) {
        Node node1 = map.get(data1);
        Node node2 = map.get(data2);

        Node parent1 = findSet(node1);
        Node parent2 = findSet(node2);

        // if they are part of same set do nothing
        if (parent1.data == parent2.data) {
            return false;
        }

        // else whoever's rank is higher becomes parent of other
        if (parent1.rank >= parent2.rank) {
            // increment rank only if both sets have same rank
            parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 : parent1.rank;
            parent2.parent = parent1;
        } else {
            parent1.parent = parent2;
        }
        return true;
    }

    public static int findSet(int data) {
        return findSet(map.get(data)).data;
    }

    private static Node findSet(Node node) {
        Node parent = node.parent;
        if (parent == node) {
            return parent;
        }
        node.parent = findSet(node.parent);
        return node.parent;
    }

    static class pair {
        int x;
        int y;

        pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Maths {
        static long gcd(long a, long b) {
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }

        public static long lcm(long a, long b) {
            return (a * b) / gcd(a, b);
        }

        public static long factorial(int n) {
            long fact = 1;
            for (int i = 1; i <= n; i++) {
                fact *= i;
            }
            return fact;
        }
    }

}