글 읽기 - 데이터 추가 요청

chinjja 3년 전 0

아래의 입력과 같이 행이 서로가 겹치지 않게 입력을 했을 경우

런타임 오류가 생겨야 하는 코드가 성공으로 통과되었습니다.

백준 데이터셋에는 이와 같은 유형이 없는거 같습니다.

입력:

A B

C D

출력

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class union_find {
public:
	union_find(size_t sz) : p(sz), c(sz, 1) {
		for (int i = 0; i < sz; i++) {
			p[i] = i;
		}
	}

	bool merge(int a, int b) {
		a = top(a);
		b = top(b);
		if (a != b) {
			p[a] = b;
			c[b] += c[a];
			return true;
		}
		return false;
	}

	bool is_merge(int a, int b) {
		return top(a) == top(b);
	}

	int top(int a) {
		if (a == p[a]) return a;
		return p[a] = top(p[a]);
	}

	int count(int a) {
		return c[top(a)];
	}

private:
	vector<int> p;
	vector<int> c;
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T, N;
	string a, b;
	cin >> T;
	while (T--) {
		cin >> N;

		union_find uf(N * 2); // <= 비정상코드 : 정상코드 => (N * 2 + 1);
		unordered_map<string, int> id;
		int last_id = 1;
		for (int i = 0; i < N; i++) {
			cin >> a >> b;
			if (!id.count(a)) {
				id[a] = last_id++;
			}
			if (!id.count(b)) {
				id[b] = last_id++;
			}
			uf.merge(id[a], id[b]);
			cout << uf.count(id[a]) << '\n';
		}
	}
	return 0;
}

startlink 3년 전 0

재채점했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

데이터 추가 요청

chinjja 3년 전 0

startlink 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말