백준 1471 - 사탕 돌리기

문제링크 : https://www.acmicpc.net/problem/1471

1부터 N까지 문제에서 말하는대로 그래프 만들어주면된다

최대 몇칸을 움직일 수 있는지 알아봐야 하는데

a컴포넌트 -> b 컴포넌트 -> c ..... 다시 a 까지 오는거를 알아보면 된다

순환되는요소(강한연결요소)가 생기는건 하나의 컴포넌트로 간주해줬다.(vector p[200001])

모든 간선들에 대해 SCC를 구하고 난 뒤에

만들어진 SCC들 끼리는 순환이 안되는게 당연하니깐

해당 SCC에서 얼마나 멀리 이동할 수 있는지 구하면된다

이는 해당 컴포넌트의 사이즈를 더해주면서 탐색을 이어 나가면 된다.

이때 indegree가 0인 요소가 여러개 있을 수 있다 그 지점들을 시작점으로 두고 탐색을 했다

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
int N;
vector<int> v[200001];
int d[200001];int sn[200001];
int idx;int sccNum;
stack<int> st;
bool finished[200001];
// scc의 관계
vector<int> p[200001];
int com[200001];
vector<vector<int>> SCC;
int indegree[200001];
int dfs(int n){
    d[n] = ++idx;
    st.push(n);
    int ret = d[n];
    for(int next : v[n]){
        if(d[next]==0)
            ret = min(ret,dfs(next));
        else if(!finished[next])
            ret = min(ret,d[next]);
    }
    
    if(ret == d[n]){
        vector<int> scc;
        while(1){
            int t = st.top();
            st.pop();
            scc.push_back(t);
            finished[t]=true;
            sn[t]=sccNum;
            if(t==n) break;
        }
        sort(scc.begin(),scc.end());
        SCC.push_back(scc);
        sccNum++;
    }
    return ret;
}
int ans = 0;
void bfs(){
    queue<int> q;
    
    for(int i=1;i<=N;i++){     
        if(indegree[sn[i]]==0){ 
            q.push(sn[i]);
            com[sn[i]]=SCC[sn[i]].size();
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans = max(ans,com[now]);

        for(int next : p[now]){
            if(com[next]<com[now]+SCC[next].size()){
                com[next]=com[now]+SCC[next].size();
                q.push(next);
            }
        }
    }
}
int main(){
    cin>>N;
    for(int i=1;i<=N;i++){
        string now=to_string(i);
        int next = 0;
        for(int t=0;t<now.size();t++){
            next+=now[t]-'0';
        }
        if(next+i>N){
            if(((next+i)%N)==0){
                v[i].push_back(i);
            }else{
                v[i].push_back((next+i)%N);
            }
           
        }else{
            v[i].push_back((next+i));   
        }
    }
    
    for(int i=1;i<=N;i++){
        if(d[i]==0) dfs(i);            
    }
    for(int i=1;i<=N;i++){
        for(int next : v[i]){
            if(sn[next]!=sn[i]){
                p[sn[i]].push_back(sn[next]);
                indegree[sn[next]]++;
            }
        }
    }
    
    bfs();
    cout<<ans;
}