9466 텀 프로젝트

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

9466번: 텀 프로젝트

 

한 학생당 한 명만 지목할 수 있으므로 단조로운 형태의 그래프가 형성된다.

위 표를 그래프로 그려보면 다음과 같다.

 

이 때, 사이클을 형성하는 그룹({3}, {4, 6, 7})만 팀에 속하고, 나머지는 팀에 속하지 못한다.

 

dfs로 해당 루트에 group number를 부여해 이미 왔던 곳인데 group number가 같다면 사이클이 형성된 것이므로 해당 갯수만큼 모두 합하여 전체 노드 갯수에서 빼면 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int target;
bool flag;
 
int dfs(int pos, int gn, vector<int>& select, vector<int>& visit)
{
    visit[pos] = gn;
    if(pos == select[pos]) return 1;
    if(visit[select[pos]] == gn)
    {
        target = select[pos];
        flag = true;
        return 1;
    }
    else if(visit[select[pos]] > 0) return 0;
    int ret = dfs(select[pos], gn, select, visit);    
    if(flag) ret++;
    if(target == pos) flag = false;
    return ret;
}
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        vector<int> visit(n+1, 0), select(n+1, 0);
        for(int i=1;i<=n;i++)
            cin >> select[i];
        int gn = 1, ans = 0;
        for(int i=1;i<=n;i++)
        {
            if(visit[i]) continue;
            ans += dfs(i, gn++, select, visit);
            flag = false;
        }
        cout << n-ans << endl;
    }
    return 0;
}