# 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

###### tags: `leetcode`,`dfs`,`medium`

>ref: https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/
>
You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.




class Solution {
    public long countPairs(int n, int[][] edges) {

        //dfs

        // tc n node + e edge 

        // sc n+e

        int[] visit = new int[n];

        Map<Integer,ArrayList<Integer>> m= new HashMap<>();

        for(int[] e:edges){
            m.computeIfAbsent(e[0],a->new ArrayList<>()).add(e[1]);
            m.computeIfAbsent(e[1],a->new ArrayList<>()).add(e[0]);
        }

        int ori=n;
        long ans=0;

        for(int i=0;i<n;i++){
            if(visit[i]==0){
                long count=dfs(visit,m,i);
                ori-=count;
                ans+=count*(ori);
                if(ori==0)break;
            }
        }

        return ans;
        
    }


    private  int dfs(int[] visit,Map<Integer,ArrayList<Integer>> m, int idx){


        int count=1;
        visit[idx]=1;

        for(int nei:m.getOrDefault(idx,new ArrayList<>())){
            if(visit[nei]==0){
                count+=dfs(visit,m,nei);
            }
        }

        return count;

    }
}