텀 프로젝트

백준 9466번: 텀 프로젝트

아이디어

그냥 dfs하면 안되고 ”학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.” 조건을 잘 걸러내야 한다. 즉 그래프에서 한바퀴 도는 경우가 생겼을 그 사람들끼리는 팀이라고 기록해줘야 한다.

코드

#include <bits/stdc++.h>

using namespace std;

// 0: not visited
// 1: checking
// 2: in team
// 3: no team

int solve(vector<int> &v) {
    int visited[v.size()] = {};
    vector<int> select;
    
    for (int i = 1; i < v.size(); i++) {
        if (visited[i] > 0) continue;
        select.push_back(i);
        int next = i;
        while (visited[next] == 0) {
            visited[next] = 1;
            next = v[next];
            select.push_back(next);
        }
        select.pop_back();
        
        if (visited[next] == 1) { // team
            auto iter = select.begin();
            while (*iter != next) {
                visited[*iter] = 3;
                iter++;
            }
            while (iter != select.end()) {
                visited[*iter] = 2;
                iter++;
            }
        }
        else { // no team
            for (int x : select) {
                visited[x] = 3;
            }
        }
        select.clear();
    }
    
    int cnt = 0;
    for (int x : visited) {
        if (x == 3) {
            cnt++;
        }
    }
    
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> v;
        v.push_back(0);
        while (n--) {
            int x;
            cin >> x;
            v.push_back(x);
        }
        cout << solve(v) << '\n';
    }
    return 0;
}

설명

visited 배열에 숫자 1을 기록하면서 탐색한다. 현재 탐색중인 학생들을 select 벡터에 집어넣는다. 그러다 다음으로 탐색할 학생의 visited자리가 1이면 한바퀴 돌아서 팀이 생긴 것이다. 이 때 한바퀴 도는데 포함되지 않은 학생들은 앞으로 영원히 팀이 없을 예정이기 때문에 visited배열에 3을 기록하고 한바퀴 도는데 포함된 학생들은 2를 기록한다.

여담

이거 그냥 그래프 사이클 찾기 문제인데 좀 복잡하게 푼듯