Challenge: How Many Friend Groups?

Lab Java Intermediate 20 points

In a class, friendships link students into groups (friends of friends are in the same group). Print the number of groups and then the size of the biggest group. Use DFS.

Input

Line 1: n m – people/places are numbered 1 to n, and there are m links. Then m lines u v: a two-way link between u and v.

Output

Line 1: groups: g. Line 2: biggest: b.

Example

Input

Output

groups: 2
biggest: 4

Sample input available Sample output available

Editor

Java

Hints

Loop over every student; if they're not seen yet, that's a new group.

Make dfs return how many students it visited.

Solution explanation

Every student and friendship is handled once: O(n + m).

Show solution

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
    static boolean[] seen;

    static int dfs(int node) {             // returns the size of the group
        seen[node] = true;
        int size = 1;
        for (int next : g.get(node)) {
            if (!seen[next]) size += dfs(next);
        }
        return size;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g.get(u).add(v);
            g.get(v).add(u);
        }
        seen = new boolean[n + 1];
        int groups = 0, biggest = 0;
        for (int p = 1; p <= n; p++) {
            if (!seen[p]) {
                groups++;
                biggest = Math.max(biggest, dfs(p));
            }
        }
        System.out.println("groups: " + groups);
        System.out.println("biggest: " + biggest);
    }
}

Output

Answer