1717번 문제인가요? n이 최대 천만이 아니고 백만이라 전부 선언해도 괜찮아요. 천만이라고 해도 int형이면 40MB 정도라서 초과는 안 날 텐데... 코드에서 원인을 찾아야겠죠.

어떻게 짜셨는지 모르겠는데..

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

요런 식으로 짜셨다면..

최대 100만까지 호출이 되어버릴 수 있어서 시간초과 + 메모리 초과 날 거 같네요.
예를 들어서 100만의 부모가 99만9999고 99만 9999번 부모가 99만 9998번이고
...
이런 식으로 계속 올라가면 말이죠.

일단 풀 소스를 보여주세요.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> parents;
int find(int n) {
if (parents[n] == -1) return n;
parents[n] = find(parents[n]);
return parents[n];
}

void merge(int a, int b) {
if (a == b) return;
a = find(a);
b = find(b);
parents[b] = a;
}

string is_equls_root(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return string("YES");
else return string("NO");
}

int main() {
int n, m;

cin >> n >> m;

parents = vector<int>(n + 1, -1);

for (int i = 0; i < m; i++) {
int operation, a, b;

cin >> operation >> a >> b;

if (operation == 0) {
merge(a, b);
}
else {
cout << is_equls_root(a, b) << endl;
}
}
}

rank까지는 잘 모르겠고..

유니온 파인드를 구현을 잘 하셨다면 find 과정에서 경로 압축을 합니다..

그러니까 다른 문제인 거 같은데..

자세히 보니까 merge 함수가 이상한데요?

예를 들어서 원래 1의 부모가 7이였고 3의 부모도 7이였다고 칩시다.

merge(1,3)을 하는 경우. 이 명령은 무시되어야 하는데. 님 코드에 따르면

1하고 3하고 다르니까 a=find(a)에서 a가 7 b도 7이 되네요.

그 결과 parent[7] = 7이 되는데. 이 상태에서 find(7)을 호출하면 무한루프가 돌지 않을까요?

두 분께 우선 감사드립니다.

chogahui05님 말씀대로 예외처리를 이상하게 해서 스택오버플로우 때문에 메모리초과를 받은 것 같네요

시간복잡도는 find()연산에 따라 달라지니 chogahui05님 말씀처럼 높이(?)가 더 높은 곳에 합칠 수 있도록(저는 사실 자식의 개수)했는데도 잘 안풀리네요ㅠㅠ

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> parents;

int find(int n) {
if (parents[n] < 0) return n;
parents[n] = find(parents[n]);
return parents[n];
}

void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (parents[a] < parents[b]) {
parents[a] += parents[b];
parents[b] = a;
}
else {
parents[b] += parents[a];
parents[a] = b;
}
}

string is_equls_root(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return string("YES");
else return string("NO");
}

int main() {
int n, m;

cin >> n >> m;

parents = vector<int>(n + 1, -1);

for (int i = 0; i < m; i++) {
int operation, a, b;

cin >> operation >> a >> b;

if (operation == 0) {
merge(a, b);
}
else {
cout << is_equls_root(a, b) << endl;
}
}
}

높은 쪽에 낮은 쪽 합치는 건 제가 한 말인데요 ㅠ

그리고 시간 초과가 뜨는 건 입출력이 느려서 그래요.

1. ios_base::sync_with_stdio(0); 를 하고 시작하면 cin, cout이 stdin, stdout과 별개의 버퍼를 가지고 동작할 수 있어 꽤 빨라집니다.

2. endl은 매우 매우 느립니다. endl은 단순 개행이 아니고, 개행을 함과 동시에 버퍼를 비우는 역할을 하기 때문에, endl 대신에 '\n'을 쓰는 것이 훨씬 좋습니다.

3. cin.tie(NULL); 도 하고 시작해야 됩니다. cin은 기본값으로 cout에 묶여있어서 cin이 호출되면 항상 cout을 flush 하고 시작하거든요.

merge 함수에서.. find(a)는 a의 root이고 find(b)는 b의 root이므로. a=find(a); b=find(b);를 수행한 후에는 a는 root_a, b는 root_b가 되겠죠.

그런데. parents[a]는 부모를 찾아가기 위해서 만들어 놓은 것입니다.

보시면 parents[a] = parents[a] + parents[b]를 해 놓으셨는데.

이러면 어떻게 될까요? 이상한 동작을 수행해 버립니다.

그러므로 parents[b] = a; 문장만 넣어주셔야 합니다.

zp 님의 의도는 최종적으로 b의 root (B)를 a의 root (A) 밑에 넣는 게 아닌가요?

이것들만 추가해서 내봤는데 32MS 뜹니다.

히익?? 후덜덜..

그러게요, 저도 다시 보니 좀 이상하네요.

생각을 해 보니까...

처음에 parents는 모두 -1로 초기화 되어있고, merge를 할 때 서로 합쳐지는 두 노드는 모두 기존 트리의 root들이죠. 그런데 둘 다 음수라면, += 을 한 결과도 음수가 나오겠고요. 그렇다면 find를 할 때 문제는 안 되겠네요.

루트가 안 된 쪽은 정확하게 새로운 루트를 부모로 가지니, 다시 find를 해도 문제는 안 생기겠네요.

결국 이건 결과적으로 봤을 때, 트리의 높이 균형은 아니고 자식/자손 노드의 수가 적은 쪽이 많은 쪽에 붙게 될 것 같아요.

아 죄송합니닷ㅠ

djm03178님이 가르쳐주신대로 높이 균형을 맞출라고 했습니다만,