For pair work, each student wrote down one friend they want to work with.
The first line gives the number of requests n, and the next n lines give the requests "a b" in the order they arrived. It means a picked b.
If a student sends several requests, only the last one counts.
A student's turn is the turn of their first request, and it does not change when they send again.
Two students x and y are mutual partners if, in the requests that count, they picked each other.
No student picks themselves. A picked friend may never have sent a request.
Print the number of mutual pairs on the first line.
Then print one line "x y" for each pair, where x is the student of the two whose turn comes first.
Print the pairs in the order of x's turn. If there are no pairs, print only the 0 on the first line.
Input
1 ≤ n ≤ 5,000. Names have 1 to 10 lowercase English letters, and the two names in a request differ
Output
The number of pairs on the first line, then one line per pair (x y) in order of x's turn
Example 1 · stdin
7
mina jun
jun sora
sora jun
dan mina
mina dan
eve kai
jun mina
stdout
1
mina dan
Example 2 · stdin
3
b a
a b
c a
stdout
1
b a
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Put the last request in a dictionary (pick[a] = b), then walk the dictionary in insertion order and check whether pick[b] == a. Overwriting the value of an existing key keeps that key where it was first inserted (Python dict, JS/TS Map, Java LinkedHashMap, the Keys of a Craykon dict). setdefault, putIfAbsent and TryAdd keep only the first request, which is wrong. Order is the trap. Java HashMap and C++ unordered_map scramble the order, and C++ std::map goes in dictionary order of the names. The documentation of C# Dictionary promises no enumeration order, so write the first-seen names in a separate list and walk that. Another trap is that a picked friend may never have sent a request. C# pick[b] throws KeyNotFoundException, so ask with TryGetValue; in Python use pick.get(b); in Craykon ask with Contains first (reading a missing key stops the program). C++ pick[b] silently inserts an empty value, so use find. If you only check for mutual picks while walking, each pair appears twice, at x's turn and at y's turn, so mark partners you have already written. C has no dictionary, so write names in an array in first-seen order and search from the front with strcmp.
Pythonmain.py · 16 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
n = Console.ReadLine().ToNumber();pick = Dict();for (i = 0; i < n; i++){ p = Console.ReadLine().Trim().Split(" "); pick[p[0]] = p[1]; // 다시 내면 값만 바뀌고 열쇠의 차례는 그대로다}pairs = [];done = Dict();// 크레이콘 사전의 열쇠목록은 처음 넣은 차례다foreach (a in pick.Keys){ b = pick[a]; if (!done.Contains(a) && pick.Contains(b)) { if (pick[b] == a) { pairs.Add(a + " " + b); done[b] = true; } }}Console.WriteLine(pairs.Count);foreach (s in pairs){ Console.WriteLine(s);}