Atcoder ACL

오늘 소개할 것은 Atcoder에서 사용할 수 있는 template 모음이다.

 

ACL은 AtCoder Library로 Atcoder 플랫폼에서 사용할 수 있는 template이다. 처음알게 된 것은 atcoder 90제 문제를 풀어보면서 다른 사람 코드를 볼 때, 확장자 헤더에 atcoder/all이 있고 코드들을 단순하게 잘 작성하길래 찾아보게 되었다.

 

https://atcoder.jp/posts/518

AtCoder Library (ACL) - AtCoder

해당 포스트에서 다운을 받을 수 있고

 

https://github.com/atcoder/ac-library?tab=readme-ov-file

GitHub - atcoder/ac-library: AtCoder Library

내부 구현 주소는 위와 같다.

 

사용법으로는 Visual Studio를 쓰는 나같은 경우는 bits/stdc++을 적용해본 사람들은 해당 파일이 있는 위치에 다운 받은 파일 중 atcoder폴더를 그대로 넣으면 된다. 위 파일을 처음 들어보는 사람은 구글에 해당파일 적용하는 방법을 검색해보면 된다.

 

https://atcoder.jp/contests/practice2/tasks

Tasks - AtCoder Library Practice Contest

위 링크로 가면 구현되어있는 자료구조들을 연습할 수 있는 문제들이 있다.

 

https://atcoder.github.io/ac-library/production/document_en/

https://atcoder.github.io/ac-library/production/document_en/

위 문서를 보고 사용법을 보면서 풀어보면 된다.

 

비록 atcoder 템플릿이 생긴 이유가 ps의 접근을 쉽게 하기 위해서 이러한 구현체들을 사용하더라도 내부 원리나 시간복잡도 또는 이를 수정할 수 있는 능력 역시 중요하다. 

 

마지막은 DSU(유니온파인드) 문제를 풀어본 내 코드이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, Q;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> Q;

	dsu d(N);

	rep(i, Q)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 0)
		{
			d.merge(b, c);
		}
		else
		{
			if (d.same(b, c))
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}