(C++) 백준 1976 여행 가자 (Union-Find)

https://www.acmicpc.net/problem/1976

처음에 메모리크기를 조건보다 잘못잡아서 메모리 초과가 났다;;
문제는 전형적인 union-find 문제이다.

• int findParent(int u) : u의 부모를 return 하는 함수
• void merge(int u, int v) : 하나로 연결되어있는 두 노드를 merge하기 위해 v의 root parent를 u의 root parent로 저장하는 함수

이렇게 Union, Find 동작을 하는 두 함수를 정의하고 문제의 조건에 맞게 사용하면 쉽게 풀수 있었다.
그런데 이문제는 N이 작기 때문에 문제가 되지 않지만 재귀함수가 자주 호출되는거 때문에 N이 커지면 문제가 될거같다 .... 다른 문제 풀면서 Union-Find 문제를 최적화해서 풀수있는 방법을 생각해봐야겠다

#include <iostream>
using namespace std;

int N,M;
int x;
int parent[205];
int path[1005];

int findParent(int u){

    if(parent[u]==u) return u;
    parent[u] = findParent(parent[u]);
    return parent[u];
}


void merge(int u, int v){
    parent[findParent(u)]=findParent(v);
}


int main(){

    ios_base::sync_with_stdio();
    cin.tie(0);
    
    cin>>N>>M;

    for(int i=1; i<=N; i++) parent[i]=i;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin>>x;
            if(x) {
                merge(i,j);
            }
        }
    }

    for(int i=0; i<M; i++) cin>>path[i];

    bool isTrue=true;

    int root = findParent(path[0]);
    for(int i=1; i<M; i++){
        if(root!=findParent(path[i])) {
            isTrue=false;
            break;
        }
    }

    if(isTrue) cout<<"YES";
    else cout<<"NO";

}