15462-The Bovine Shuffle(Silver)

15462-The Bovine Shuffle(Silver)

Bronze문제처럼 셔플 규칙 수열이 제시되는데, 이번에는 그 규칙대로 무한히 많이 셔플한다고 가정할 때 소가 항상 위치하게 되는 지점의 개수를 묻고 있다. 이 문제에서 셔플 수열은 같은 수가 등장할 수도 있어서 그런 경우에는 한 지점의 여러 마리의 소들이 위치하게 되고, 그 말은 즉슨 어느 지점은 아무 소도 위치하지 않는다는 뜻이다.  어떻게 풀지 끄적거리다가 셔플이라는 행위 자체를 그래프로 모델링하니 쉽게 와닿았다. 

예를 들어 3 2 1 3이라는 셔플 수열의 의미는 다음 번에 1번 지점의 소는 3번으로, 2번지점의 소는 2번으로.... 이런 의미이고, 이를 그래프로 모델링하면 다음과 같다.

위와 같은 그래프가 있다고 가정하고, 각 노드에서 다음 노드를 향해 움직인다고 생각해보자. 그러면 1은 3으로,3은 1로, 4는 3으로, 2는 2로간다. 다시 말해 1,3,2는 소가 여전히 남아있지만, 4는 자신을 가리키고 있는 노드가 없으므로 아무 소도 존재하지 않게 된다. 그리고 여기서부터는 무수히 많이 반복한다 하더라도 1,2,3 노드만 소가 존재하고, 4는 계속 소가 존재하지 않는다.

그렇다면 1,2,3노드와 4번 노드의 차이는 무엇일까? 그건 바로 사이클의 존재 여부이다. 1,2,3번 노드는 사이클의 구성 요소이다. 그런 노드의 개수가 곧 답이 되는 것이다. 

그럼 이제 문제는 그래프에서 사이클인 노드의 개수를 카운트하는게 문제가 된다. 그런 알고리즘으로는 SCC가 있다. 다만 일반적인 SCC는 (셀프사이클이 아님에도)오직 하나의 노드로만 구성된 SCC도 카운트된다는 점이다. (위 그래프에서 4번 노드가 이에 해당한다.) 그런 노드는 제외시켜주어야 하므로 따로 예외처리를 해주어야 한다. 아래는 그렇게 묶은 결과이다.

#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>
#define SIZE 100010
using namespace std;
vector <int> v[SIZE];
vector<int> scc[SIZE];
stack<int> s;
bool visited[SIZE] = { false };
int cnt = 1, idx[SIZE], low[SIZE], scc_cnt = 0,ans=0;
int min(int a, int b) {
    return a > b ? b : a;
}
void dfs(int cur) {
    low[cur] = cnt;    idx[cur] = cnt++; 
    s.push(cur);
    visited[cur] = true;
    for (int next : v[cur]) {
 
        if (idx[next] == 0) {
            dfs(next);
            low[cur] = min(low[cur], low[next]);
        }
        else if (visited[next])
            low[cur] = min(low[cur], low[next]);
    }
 
    bool flag=false;
    if (idx[cur] == low[cur]) {
        if(cur!=s.top())
            flag=true;
        
        while (1) {
            int top = s.top();    s.pop();
            scc[scc_cnt].push_back(top);
            visited[top] = false;
 
            if(flag) ans++;
            if (idx[top] == low[top]) {
                break;
            }
        }
    }
}
int main() {
    int V;    scanf("%d", &V);
 
    for(int i=1 ; i<=V ; i++){
        int dest;    scanf("%d",&dest);
        if(i==dest) ans++;
        v[i].push_back(dest);
    }
    
 
    for (int i = 1; i <= V; i++) {
        if (idx[i] == 0)    dfs(i);
    }
 
    printf("%d\n",ans);
 
    return 0;
}