codeforces #603 div2 D - Secrete Passwords ( 이분매칭, disjoint set )

http://codeforces.com/contest/1263/problem/D

 

editorial은 biparite graph 어쩌고로 풀던데, 나는 유파로 풀었다.

 

<문제설명>

문자열이 최대 2e5개 들어온다.

. i번째 문자열과 j번째 문자열이 단 한 개라도 같은 알파벳을 사용했다면 두 문자열은 equivalent다

. k번째와 i번째 문자열이 equivalent하고 k번째와 j번째 문자열이 equivalent하다면 i번째와 j번째는 equivalent다.

 

위 상황에서 컴포넌트의 수를 구하는 문제이다. 간선만 잘 깔아주면 된다. 하지만 n이 커서 단순히 모든 요소를 비교하는 식으로 간선을 이을 수 없다. 

 

<풀이>

bool s[MAX][26] = { 0 };

string 형으로 문자열을 입력받은 후, 위에 저장해 뒀다. ( ab입력시 110000... 저장되는 식 )

 

그리고 모든 알파벳에 대해 그 알파벳을 포함하는 애들끼리 유파해줬다. (두번째 조건 때문에 그냥 다 이어버리면 된다.)

 

결과 그래프에서 모든 연속된 순서의 정점끼리 merge할 수 있으면 컴포넌트 수++ 해주었다.

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int MAX = 2e5 + 1;

int uf[MAX];

int find(int a) {
	if (uf[a] == -1) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[a] = b;
	return true;
}

int main() {
	int n; cin >> n;
	bool s[MAX][26] = { 0 };
	for (int i = 0; i < n; i++) {
		string input; cin >> input;
		for (int j = 0; j < input.size(); j++) 
			s[i][input[j] - 'a'] = true;
	}

	fill(uf, uf + MAX, -1);

	for (int i = 0; i < 26; i++) {
		vector<int> cand;
		for (int j = 0; j < n; j++) 
			if (s[j][i]) cand.push_back(j);

		if (cand.size() <= 1) continue;

		for (int j = 0; j < cand.size() - 1; j++) 
			merge(cand[j], cand[j + 1]);
	}

	int ans = 1;
	for (int i = 0; i < n - 1; i++)
		if (merge(i, i + 1)) ans++;

	cout << ans << '\n';
}

 

 

 

<후기>

뭔가 만들다 만 문제같다.