BOJ 9466. 텀 프로젝트

랭크 : 골드3

문제 풀이

그래프를 돌면서 순환이 일어나는 구간을 체크하는 것이 중요하다. 한번 체크하고 나면 두번 다시 체크할 일이 없으므로 부모를 -1로 바꿔주어, 두번 체크하지 않게합니다. 방문한 곳을 두번 체크하지 않기 위해서 union_find를 활용하였는데, 잘 생각해보니 visited 배열에 dfs를 활용하는게 더 깔끔하고 빠르게 풀었을 것 같습니다..

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int T, N;
int favor[100'001];
int parents[100'001];

int findParents(int i) {
    if (parents[i] == i) return i;
    else return parents[i] = findParents(parents[i]);
}

void UnionFind(int x, int y) {
    x = findParents(x); y = findParents(y);
    parents[x] = y;
}

bool isUnion(int x, int y) {
    x = findParents(x); y = findParents(y);
    return (x == y);
}

int main() {
    fastio;
    cin >> T;
    while (T--) {
        int ans = 0;
        cin >> N;
        for (int i=1; i <= N; i++) {
            cin >> favor[i]; parents[i] = i;
        };
        for (int i=1; i <= N; i++) {
            if (parents[i] == -1) continue;
            int tmp = i;
            vector<int> q;
            q.push_back(tmp);
            while (parents[favor[tmp]] != -1 && !isUnion(tmp, favor[tmp])) {
                UnionFind(tmp, favor[tmp]);
                tmp = favor[tmp];
                q.push_back(tmp);
            }
            tmp = favor[tmp];
            int j = 0;
            while (j < q.size() && q[j] != tmp) {
                parents[q[j]] = -1;
                j++;
                ans++;
            };
            for (; j< q.size(); j++) {
                parents[q[j]] = -1;
            };
        };
        cout << ans << endl;
    }

}

`알고리즘`	`시간복잡도`	`공간복잡도`
union_find, 그래프	$O(N)$	$O(N)$

```