[DFS] BJ2668 숫자 고르기

문제 출처: https://www.acmicpc.net/problem/2668

 

Solution

•  
• DFS하면서 cycle이 존재하면 result set에 넣는다. 
• DFS call할 때, 시작점을 넘기고, next 노드가 시작 노드와 같으면 cycle 존재한다.

Point

• cycle 생기면 방문했던 노드들 넣으면 되는데, 중복 생길 수 있기 때문에, 제거하거나 result에 넣은 것들은 2를 줘서 구분해서 안 넣도록 해야 함

---

#include <iostream>    
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int list[101];
int visited[101];
vector<int> result;

void input() {
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> list[i];
}

void initVisit() {
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < result.size(); i++)
        visited[result[i]] = 2;    //이미 result에 들어간 노드는 2로 
}

bool dfs(int start, int cur) {
    visited[cur] = 1;
    int next = list[cur];
    if (next == start) { //cycle
        for (int i = 1; i <= N; i++) {
            if (visited[i]==1) //cycle 만들며 방문했던 노드 모두 result에 넣는다.
                result.push_back(i);
        }
        return 0;
    }
    if (!visited[next])
        dfs(start, next);
    return 0;
}

void searchDFS() {
    for (int i = 1; i <= N; i++) {
        initVisit();
        dfs(i, i);
    }
}

int main()
{
    input();
    searchDFS();
    sort(result.begin(), result.end());
    //result.erase(unique(result.begin(), result.end()), result.end());
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << endl;
}