You are viewing a single comment's thread. Return to all comments →
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); final int N = Integer.parseInt(line[0]); final List<List<Integer>> compatriots = new ArrayList<List<Integer>>(N); for(int i = 0; i < N; ++i){ compatriots.add(new ArrayList<Integer>()); } for(short L = Short.parseShort(line[1]); L > 0; --L){ line = br.readLine().split(" "); final int A = Integer.parseInt(line[0]); final int B = Integer.parseInt(line[1]); compatriots.get(A).add(B); compatriots.get(B).add(A); } boolean[] isVisited = new boolean[N]; List<Integer> countrySizes = new ArrayList<Integer>(); for(int i = 0; i < N; ++i){ int countrySize = 0; final Queue<Integer> q = new ArrayDeque<Integer>(); q.add(i); do { int astronautId = q.poll(); if(!isVisited[astronautId]){ ++countrySize; isVisited[astronautId] = true; q.addAll(compatriots.get(astronautId)); } } while (!q.isEmpty()); if(countrySize > 0){ countrySizes.add(countrySize); } } long numPairs = 0L; long numPartners = N; for(int countrySize : countrySizes){ numPairs += countrySize * (numPartners -= countrySize); } System.out.print(numPairs); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →