1. dfs + cycle 문제입니다. 특이점은 visit, finish 배열을 사용하나는 점입니다. dfs 의 구조를 보면 먼저 방문은 시작하고 다음 next를 찾습니다. 그리고 visit 가 0이면 들어가고 끝났는지 확인해서 끝나지 않았으면 들어가서, 역순회를 하도록 합니다. 오께이 그렇게 역순회를 마치지고, 자기 자신까지 ++ 을 하고 나서 나와줍니다. 만약에 비지트가 안되어있다면, 비지트에 넥스트를 넣고 dfs를 다시 들어갑니다. 그리고 else 가 끝이 나면, finish 를 해둡니다. 오께이. 그다음에 solve 함수에서는 i=0 부터 N 까지 해줍니다. visit 가 0이면 들어가도록 합니다. 오께이. 아직은 하나씩 짜기가 쉽지 않으니, 오께이. |
처음에 인덱스가 0부터 시작하니까 처음입력 받을때 -- 처리를 한 것입니다. int N; int S[SIZE]; int cnt; visit, finish 가 있습니다. dfs 함수에는 int cur 하나가 들어갑니다. 그리고 visit next visit if finish 역 순회 오꼐이. cnt++ 자기 자신 ++ gkqslek. else 에는 dfs(next) 를 해서 visit 하도록 합니다. 오께이. void sovle 에는 for(int i=0; i<N; i++) 를 넣고, if(!visit[i]) } dfs(i); 를 넣습니다. |
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220785731077 |
#include <iostream> #include <algorithm> #include <cstdio> #include <memory.h> using namespace std; #define SIZE 100000 int N; int S[SIZE]; int cnt; // 싸이클에 속하는 정점의 개수 bool visit[SIZE]; bool finish[SIZE]; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { cin >> S[i]; S[i]--; } memset(visit, 0, sizeof(visit)); memset(finish, 0, sizeof(finish)); cnt = 0; } void dfs(int cur) { visit[cur] = 1; int next = S[cur]; if (visit[next]) { if (!finish[next]) { for (int temp = next; temp != cur; temp = S[temp]) { cnt++; } cnt++; } } else dfs(next); finish[cur] = 1; } void solve() { for (int i = 0; i < N; i++) { if (!visit[i]) { dfs(i); } } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << N - cnt << endl; } return 0; } |