辞書の走査P0256

互いに選んだペアを探す

ペア活動のために、生徒がいっしょに組みたい友だちを一人ずつ書いて出した。
一行目に申し込みの数 n、続く n 行に届いた順に申し込み "a b" が与えられる。
a が b を選んだという意味である。
同じ生徒が何度も申し込んだら、最後の申し込みだけが残る。
生徒の順番はその生徒が初めて申し込んだ順番で、申し込み直しても変わらない。
二人の生徒 x、y が残った申し込みで互いを選んでいれば、互いのペアである。
生徒は自分自身を選ばない。
選ばれた友だちが一度も申し込んでいないこともある。
一行目に互いのペアの組の数を出力せよ。
続いて組ごとに一行に "x y" を出力する。
x は二人のうち順番が先の生徒である。
組は x の順番に出力する。
組がなければ一行目の 0 だけを出力する。

入力: 1 ≤ n ≤ 5,000。
名前は英小文字 1〜10 文字で、一つの申し込みの二つの名前は異なる
出力: 一行目に組の数、続いて組ごとに一行（x y）、x の順番

例 1 · stdin

7
mina jun
jun sora
sora jun
dan mina
mina dan
eve kai
jun mina

stdout

1
mina dan

例 2 · stdin

3
b a
a b
c a

stdout

1
b a

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

最後の申し込みを辞書に入れ（pick[a] = b）、その辞書を入れた順に回って pick[b] == a かを見ればできます。
すでにあるキーの値を入れ直しても、そのキーの順番は最初に入れた位置のままです（Python dict、JS・TS Map、Java LinkedHashMap、Craykon の辞書の キー一覧）。
最初の申し込みだけを残す setdefault・putIfAbsent・TryAdd は間違いです。
順番が落とし穴です。
Java HashMap と C++ unordered_map は順番がばらばらになり、C++ std::map は名前の辞書順で回ります。
C# Dictionary の回る順番はドキュメントが約束していないので、初めて申し込んだ名前を別のリストに書いてそのリストを回ります。
選ばれた友だちが申し込んでいないかもしれないことも落とし穴です。
C# pick[b] は KeyNotFoundException を投げるので TryGetValue で、Python は pick.get(b) で、Craykon は 含む で先に聞きます（ないキーを読むと止まります）。
C++ pick[b] はエラーなしに空の値を新しく入れてしまうので find を使います。
辞書を回りながら互いに選んだかだけを見ると、同じ組が x の順番と y の順番で二回出るので、書いたペアに印をつけておきます。
C には辞書がないので、初めて申し込んだ順に配列に書き、strcmp で先頭から探します。

Pythonmain.py · 16 行

n = int(input())pick = {}for _ in range(n):    a, b = input().split()    pick[a] = b  # 다시 내면 값만 바뀌고, 열쇠의 차례(처음 넣은 차례)는 그대로다pairs = []done = set()for a, b in pick.items():  # dict는 열쇠를 처음 넣은 차례대로 돈다    if a in done:        continue    if pick.get(b) == a:        pairs.append(f"{a} {b}")        done.add(b)  # b 차례가 와도 같은 쌍을 다시 쓰지 않는다print(len(pairs))for p in pairs:    print(p)

JavaScriptmain.js · 18 行

const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 처음 넣은 차례대로 돈다. set으로 값을 바꿔도 차례는 그대로다const pick = new Map();for (let i = 1; i <= n; i++) {  const [a, b] = lines[i].trim().split(" ");  pick.set(a, b);}const pairs = [];const done = new Set();for (const [a, b] of pick) {  if (done.has(a)) continue;  if (pick.get(b) === a) {    pairs.push(`${a} ${b}`);    done.add(b);  }}console.log([String(pairs.length), ...pairs].join("\n"));

TypeScriptmain.ts · 19 行

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 처음 넣은 차례대로 돈다. set으로 값을 바꿔도 차례는 그대로다const pick = new Map<string, string>();for (let i = 1; i <= n; i++) {  const [a, b] = lines[i].trim().split(" ");  pick.set(a, b);}const pairs: string[] = [];const done = new Set<string>();for (const [a, b] of pick) {  if (done.has(a)) continue;  if (pick.get(b) === a) {    pairs.push(`${a} ${b}`);    done.add(b);  }}console.log([String(pairs.length), ...pairs].join("\n"));

JavaMain.java · 35 行

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashSet;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.Set; public class Main {    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        // HashMap은 차례가 뒤섞인다. LinkedHashMap은 처음 넣은 차례를 지키고, put으로 값을 바꿔도 차례는 그대로다        Map<String, String> pick = new LinkedHashMap<>();        for (int i = 0; i < n; i++) {            String[] p = br.readLine().trim().split(" ");            pick.put(p[0], p[1]);        }        List<String> pairs = new ArrayList<>();        Set<String> done = new HashSet<>();        for (Map.Entry<String, String> e : pick.entrySet()) {            String a = e.getKey(), b = e.getValue();            if (done.contains(a)) continue;            if (a.equals(pick.get(b))) {   // b가 신청하지 않았으면 get은 null                pairs.add(a + " " + b);                done.add(b);            }        }        StringBuilder out = new StringBuilder();        out.append(pairs.size()).append('\n');        for (String s : pairs) out.append(s).append('\n');        System.out.print(out);    }}

C#Main.cs · 37 行

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        // Dictionary의 도는 차례는 문서가 약속하지 않으니, 처음 신청한 차례를 목록에 따로 적는다        var pick = new Dictionary<string, string>();        var order = new List<string>();        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            if (!pick.ContainsKey(p[0])) order.Add(p[0]);            pick[p[0]] = p[1];        }        var pairs = new List<string>();        var done = new HashSet<string>();        foreach (string a in order)        {            string b = pick[a];            if (done.Contains(a)) continue;            // pick[b]는 b가 신청하지 않았으면 KeyNotFoundException — TryGetValue로 묻는다            if (pick.TryGetValue(b, out string back) && back == a)            {                pairs.Add(a + " " + b);                done.Add(b);            }        }        var sb = new StringBuilder();        sb.Append(pairs.Count).Append('\n');        foreach (string s in pairs) sb.Append(s).Append('\n');        Console.Write(sb);    }}

C++main.cpp · 33 行

#include <iostream>#include <string>#include <unordered_map>#include <unordered_set>#include <vector> int main() {    std::ios::sync_with_stdio(false);    int n;    std::cin >> n;    // std::map은 이름의 사전 순으로, unordered_map은 뒤섞인 차례로 돈다. 처음 신청한 차례는 따로 적는다    std::unordered_map<std::string, std::string> pick;    std::vector<std::string> order;    for (int i = 0; i < n; i++) {        std::string a, b;        std::cin >> a >> b;        if (pick.find(a) == pick.end()) order.push_back(a);        pick[a] = b;    }    std::vector<std::string> pairs;    std::unordered_set<std::string> done;    for (const std::string& a : order) {        if (done.count(a)) continue;        const std::string& b = pick[a];        auto it = pick.find(b);   // pick[b]로 물으면 없는 b가 빈 값으로 생긴다        if (it != pick.end() && it->second == a) {            pairs.push_back(a + " " + b);            done.insert(b);        }    }    std::cout << pairs.size() << "\n";    for (const std::string& s : pairs) std::cout << s << "\n";}

Cmain.c · 45 行

#include <stdio.h>#include <string.h> /* C에는 사전이 없어서, 처음 신청한 차례대로 이름과 고른 친구를 배열에 적고 앞에서부터 찾는다 */#define MAXN 5000static char name[MAXN][11];static char pick[MAXN][11];static int done[MAXN];static int kinds = 0; static int find(const char *s) {    for (int i = 0; i < kinds; i++)        if (strcmp(name[i], s) == 0) return i;    return -1;} int main(void) {    int n;    char a[16], b[16];    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%15s %15s", a, b);        int k = find(a);        if (k < 0) {            k = kinds++;            strcpy(name[k], a);        }        strcpy(pick[k], b);   /* 다시 내면 고른 친구만 바뀐다 */    }    int count = 0;    static int first[MAXN], second[MAXN];    for (int i = 0; i < kinds; i++) {        if (done[i]) continue;        int j = find(pick[i]);        if (j >= 0 && strcmp(pick[j], name[i]) == 0) {            first[count] = i;            second[count] = j;            count++;            done[j] = 1;        }    }    printf("%d\n", count);    for (int k = 0; k < count; k++) printf("%s %s\n", name[first[k]], name[second[k]]);    return 0;}

Craykonmain.cray · 27 行

n = コンソール.行読み().数に();pick = 辞書();繰り返す (i = 0; i < n; i++){    p = コンソール.行読み().空白除去().分ける(" ");    pick[p[0]] = p[1]; // 다시 내면 값만 바뀌고 열쇠의 차례는 그대로다}pairs = [];done = 辞書();// 크레이콘 사전의 열쇠목록은 처음 넣은 차례다それぞれ (a の中 pick.キー一覧){    b = pick[a];    もし (!done.含む(a) && pick.含む(b))    {        もし (pick[b] == a)        {            pairs.追加(a + " " + b);            done[b] = 真;        }    }}コンソール.書く(pairs.個数);それぞれ (s の中 pairs){    コンソール.書く(s);}