문제링크 :https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만
www.acmicpc.net
문제설명
1. 학생의 수가 주어지고 각 학생이 팀을이루고 싶은 사람을 지목한다
2. 서로 지목을 하거나 지목한 사람끼리 사이클을 이룬다면 팀을 이룰 수있다.
3. 팀을 이루지 못한 사람의 수를 출력
알고리즘
1. 재귀함수 를 이용하여 컴포넌트의 수를 구하는데 ,,
2. done 배열을 이용하여 해당 노드를 더이상 방문 하지않아도 되는 것을 표시하는 한다
- 만약 해당 학생이 이미 사이클을 이룬다면 더이상 방문 하지 않아도됨.
3. 방문한적이 있는데(visited[i] = 1) 끝난 노드(done[i]=0)가 아니다 ->사이클을 이룬다
- 사이클을 이루면 해당 사이클의 인원수를 세어준다 . (for문을 이용하는데 코드 꼭 참고 개중요)
4. 팀을 이루지 못한 사람의 수를 출력.
코드
|
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
53
54
55
56
57
58
59
60
61
|
#include<iostream>
using namespace std;
int N, cnt;
int line[100001];
bool visited[100001];
bool done[100001]; // 방문종료 여부
void DFS(int node) {
visited[node] = 1;
int next = line[node];
//방문한적이없으면 재귀
if (!visited[next]) DFS(next);
//방문한적이 있는데 끝난노드가 아니다.->사이클을이룸
else if (!done[next]) {
//팀원의 수를샘 , for문 중요
for (int i = next; i != node; i = line[i])cnt++;
cnt++;
}
done[node] = 1;
}
void reset(int num) {
for (int i = 0; i < num; i++) {
visited[i] = 0;
line[i] = 0;
done[i] = 0;
}
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
reset(N);
for (int j = 1; j <= N; j++) {
cin >> line[j];
}
//팀을이룬사람의수
cnt = 0;
for (int j = 1; j <= N; j++) {
if (!visited[j])
DFS(j);
}
//팀을이루지못한 사람의수
cout << N - cnt << endl;
}
}
|
cs |
참고한 블로그 : https://jaimemin.tistory.com/674
문제링크 :https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만
www.acmicpc.net
문제설명
1. 학생의 수가 주어지고 각 학생이 팀을이루고 싶은 사람을 지목한다
2. 서로 지목을 하거나 지목한 사람끼리 사이클을 이룬다면 팀을 이룰 수있다.
3. 팀을 이루지 못한 사람의 수를 출력
알고리즘
1. 재귀함수 를 이용하여 컴포넌트의 수를 구하는데 ,,
2. done 배열을 이용하여 해당 노드를 더이상 방문 하지않아도 되는 것을 표시하는 한다
- 만약 해당 학생이 이미 사이클을 이룬다면 더이상 방문 하지 않아도됨.
3. 방문한적이 있는데(visited[i] = 1) 끝난 노드(done[i]=0)가 아니다 ->사이클을 이룬다
- 사이클을 이루면 해당 사이클의 인원수를 세어준다 . (for문을 이용하는데 코드 꼭 참고 개중요)
4. 팀을 이루지 못한 사람의 수를 출력.
코드
|
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
53
54
55
56
57
58
59
60
61
|
#include<iostream>
using namespace std;
int N, cnt;
int line[100001];
bool visited[100001];
bool done[100001]; // 방문종료 여부
void DFS(int node) {
visited[node] = 1;
int next = line[node];
//방문한적이없으면 재귀
if (!visited[next]) DFS(next);
//방문한적이 있는데 끝난노드가 아니다.->사이클을이룸
else if (!done[next]) {
//팀원의 수를샘 , for문 중요
for (int i = next; i != node; i = line[i])cnt++;
cnt++;
}
done[node] = 1;
}
void reset(int num) {
for (int i = 0; i < num; i++) {
visited[i] = 0;
line[i] = 0;
done[i] = 0;
}
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
reset(N);
for (int j = 1; j <= N; j++) {
cin >> line[j];
}
//팀을이룬사람의수
cnt = 0;
for (int j = 1; j <= N; j++) {
if (!visited[j])
DFS(j);
}
//팀을이루지못한 사람의수
cout << N - cnt << endl;
}
}
|
cs |
참고한 블로그 : https://jaimemin.tistory.com/674
