Notice
Recent Posts
Recent Comments
Link
250x250
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 알고스팟
- 스택
- Algospot
- 그리디
- 알고리즘문제해결전략
- 동적계획법
- DFS
- BFS
- acm
- 완전탐색
- 세그먼트트리
- union-find
- 재귀
- 분할정복
- stack
- Greedy
- DP
- 다이나믹프로그래밍
- 백트래킹
- BOJ
- backtracking
- 이분탐색
- 문자열
- priority_queue
- 분리집합
- 유니온파인드
- 누적합
- 종만북
- 백준
- 너비우선탐색
Archives
- Today
- Total
DAMPER's 낙서장
9466 텀 프로젝트 본문
728x90
https://www.acmicpc.net/problem/9466
한 학생당 한 명만 지목할 수 있으므로 단조로운 형태의 그래프가 형성된다.
위 표를 그래프로 그려보면 다음과 같다.
이 때, 사이클을 형성하는 그룹({3}, {4, 6, 7})만 팀에 속하고, 나머지는 팀에 속하지 못한다.
dfs로 해당 루트에 group number를 부여해 이미 왔던 곳인데 group number가 같다면 사이클이 형성된 것이므로 해당 갯수만큼 모두 합하여 전체 노드 갯수에서 빼면 문제를 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#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;
}
|
cs |
728x90
'Problem Solving > BOJ 문제풀이' 카테고리의 다른 글
9328 열쇠 (0) | 2021.08.17 |
---|---|
2473 세 용액 (0) | 2021.08.17 |
1655 가운데를 말해요 (0) | 2021.05.14 |
11404 플로이드 (0) | 2021.05.14 |
11660 구간 합 구하기 5 (0) | 2021.05.14 |