그래프 연습: 연결 구역 크기를 작은 순서로 출력하기

'use strict';
class Graph {
    constructor(directed = false) {
        this.directed = directed;
        this.adj = new Map();
    }
    addVertex(vertex) {
        if (typeof vertex !== 'string') throw new TypeError('vertex must be a string');
        if (! this.adj.has(vertex)) this.adj.set(vertex,[]);
        return this;
    }
    addEdge(from, to) {
        this.addVertex(from);
        this.addVertex(to);
        this.adj.get(from).push(to);
        if (! this.directed) this.adj.get(to).push(from);
        return this;
    }
    hasEdge(from, to) {
        return this.adj.get(from)?.includes(to) ?? false;
    }
    toMatrix() {
        const vertices = [... this.adj.keys()];
        const indices = new Map(vertices.map((vertex, index) => [vertex, index]));
        const matrix = Array.from( {
            length : vertices.length
        },
        () => new Array(vertices.length).fill(0));
        for (const[from, neighbors] of this.adj) {
            for (const to of neighbors) matrix[indices.get(from)][indices.get(to)] = 1;
        }
        return {
            vertices, matrix
        };
    }
    bfs(start) {
        if (! this.adj.has(start)) return [];
        const visited = new Set([start]);
        const queue = [start];
        let head = 0;
        while (head < queue.length) {
            const vertex = queue[head];
            head += 1;
            for (const next of this.adj.get(vertex)) {
                if (visited.has(next)) continue;
                visited.add(next);
                queue.push(next);
            }
        }
        return queue;
    }
}
function solve( {
    vertices, edges
}) {
    const graph = new Graph();
    for (const vertex of vertices) graph.addVertex(vertex);
    if (graph.adj.size !== vertices.length) throw new TypeError('duplicate vertex');
    for (const[from, to] of edges) {
        if (! graph.adj.has(from) || ! graph.adj.has(to)) {
            throw new TypeError('edge endpoint is not in vertices');
        }
        graph.addEdge(from, to);
    }
    const visited = new Set();
    const sizes = [];
    for (const start of vertices) {
        if (visited.has(start)) continue;
        const queue = [start];
        visited.add(start);
        let head = 0;
        while (head < queue.length) {
            const vertex = queue[head];
            head += 1;
            for (const next of graph.adj.get(vertex)) {
                if (visited.has(next)) continue;
                visited.add(next);
                queue.push(next);
            }
        }
        sizes.push(queue.length);
    }
    return sizes.sort((a, b) => a - b);
}

from collections import deque
def solve(input):
    vertices, edges = input['vertices'], input['edges']
    adj = {v: [] for v in vertices}
    if len(adj) != len(vertices): raise ValueError('duplicate vertex')
    for a,b in edges:
        if a not in adj or b not in adj: raise ValueError('unknown endpoint')
        adj[a].append(b)
        adj[b].append(a)
    seen, sizes = set(), []
    for start in vertices:
        if start in seen: continue
        seen.add(start)
        q, size = deque([start]), 0
        while q:
            v = q.popleft()
            size += 1
            for w in adj[v]:
                if w not in seen:
                    seen.add(w)
                    q.append(w)
        sizes.append(size)
    return sorted(sizes)

import java.util.*;
class Solution {
    public int[] solve(String[] vertices, String[][] edges) {
        Map < String, List < String >> adj = new HashMap < >();
        for (String v : vertices) {
            if (adj.put(v, new ArrayList < >()) != null) throw new IllegalArgumentException("duplicate vertex");
        }
        for (String[] e : edges) {
            if (! adj.containsKey(e[0]) || ! adj.containsKey(e[1])) throw new IllegalArgumentException("unknown endpoint");
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        Set < String > seen = new HashSet < >();
        List < Integer > out = new ArrayList < >();
        for (String s : vertices) {
            if (! seen.add(s)) continue;
            Queue < String > q = new ArrayDeque < >();
            q.add(s);
            int count = 0;
            while (! q.isEmpty()) {
                String v = q.remove();
                count++;
                for (String w : adj.get(v)) if (seen.add(w)) q.add(w);
            }
            out.add(count);
        }
        Collections.sort(out);
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <stdexcept>
std::vector < int > solve(const std::vector < std::string > & vertices, const std::vector < std::vector < std::string >> & edges) {
    std::unordered_map < std::string, std::vector < std::string >> adj;
    for (const auto & v : vertices) if (! adj.emplace(v, std::vector < std::string > {
    }).second) throw std::invalid_argument("duplicate vertex");
    for (const auto & e : edges) {
        if (! adj.count(e[0]) || ! adj.count(e[1])) throw std::invalid_argument("unknown endpoint");
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    std::unordered_set < std::string > seen;
    std::vector < int > out;
    for (const auto & s : vertices) {
        if (! seen.insert(s).second) continue;
        std::queue < std::string > q;
        q.push(s);
        int count = 0;
        while (! q.empty()) {
            auto v = q.front();
            q.pop();
            count++;
            for (const auto & w : adj[v]) if (seen.insert(w).second) q.push(w);
        }
        out.push_back(count);
    }
    std::sort(out.begin(), out.end());
    return out;
}

using System;
using System.Collections.Generic;
public class Solution {
    public int[] Solve(string[] vertices, string[][] edges) {
        var adj = new Dictionary < string, List < string >>();
        foreach(string v in vertices) {
            if (adj.ContainsKey(v)) throw new ArgumentException("duplicate vertex");
            adj.Add(v, new List < string >());
        }
        foreach(var e in edges) {
            if (! adj.ContainsKey(e[0]) || ! adj.ContainsKey(e[1])) throw new ArgumentException("unknown endpoint");
            adj[e[0]].Add(e[1]);
            adj[e[1]].Add(e[0]);
        }
        var seen = new HashSet < string >();
        var result = new List < int >();
        foreach(string s in vertices) {
            if (! seen.Add(s)) continue;
            var q = new Queue < string >();
            q.Enqueue(s);
            int count = 0;
            while (q.Count > 0) {
                string v = q.Dequeue();
                count++;
                foreach(string w in adj[v]) if (seen.Add(w)) q.Enqueue(w);
            }
            result.Add(count);
        }
        result.Sort();
        return result.ToArray();
    }
}