[BOJ 15462] The Bovine Shuffle

https://www.acmicpc.net/problem/15462

15462번: The Bovine Shuffle

Tag : permutation graph

 

문제요약

permutaion graph를 몇번을 전이시키던 항상 비어있지 않은 정점의 개수를 구하는 문제다.

 

풀이

permuation graph라 매우 쉽지만 여러가지 풀이로 짜봤다.

 

sol1) kosaraju (scc)

처음에 무지성으로 코사라주를 짰다. 코사라주는 설명만 읽어봤었는데 그냥 한번 해볼때도 됐지 싶어서 짜봤다.

* 크기가 1인 사이클이 존재하는 것도 정답에 포함해야한다. 

 

시간복잡도 : \(O(N)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,ans=0,scc=0;
int chk[101010];
vector<int>vertex;
vector<int>v[101010];
vector<int>re[101010];
stack<int>st;

void dfs(int x){
    chk[x]=1;
    for(auto&i:v[x]){
        if(chk[i])continue;
        dfs(i);
    }
    st.push(x);
}

void rdfs(int x){
    chk[x]=1;
    vertex.pb(x);
    for(auto&i:re[x]){
        if(chk[i])continue;
        rdfs(i);
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>N;
    for(int i=1;i<=N;i++){
        int x;cin>>x;
        if(i==x)chk[i]=1,++ans;
        else v[i].pb(x),re[x].pb(i);
    }
    for(int i=1;i<=N;i++)if(!chk[i])dfs(i);
    memset(chk,0,sizeof chk);
    while(siz(st)){
        auto cur=st.top();st.pop();
        if(chk[cur])continue;
        vertex.clear(); 
        rdfs(cur);
        if(siz(vertex)>1)ans+=siz(vertex);
    }
    cout<<ans<<endl;
}

---

sol2) sparse table

조금 tricky하다. permuataion graph에서는 한 정점에 하나의 간선만 연결돼있다.

그래서 sparse table을 사용할 수 있고 사이클의 크기는 최대 N이기 때문에 적당히 N보다 큰 \(2^{18}\)번을 전이시켜보고

개수를 세어주면된다.

 

시간복잡도 : \(O(NlogN)\)

 

전체 코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,ans=0;
int pa[101010][20];
int chk[101010];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>N;
    for(int i=1;i<=N;i++)cin>>pa[i][0];
    for(int j=1;j<=18;j++)for(int i=1;i<=N;i++)pa[i][j]=pa[pa[i][j-1]][j-1];
    for(int i=1;i<=N;i++){
        int x=pa[i][18];
        if(x)ans+=++chk[x]==1;
    }
    cout<<ans<<endl;
}

---

sol3) naive

서로 다른 사이클마다 원소를 분리할 필요까지는 없다. 분리한다해도 permuation graph이기 때문에 굉장히 쉽다.

그래서 kosaraju같은 알고리즘을 쓰는 것은 어어엄청난 뇌절이다. 

 

탐색을 하면서 백엣지를 만났을 때 현재까지 왔던 경로를 되돌아가면된다.

* 크기가 1인 사이클도 고려해야한다!

 

시간복잡도 : \(O(N)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,ans=0,center=0;
int pa[101010];
int chk[101010];

void dfs(int x){
    chk[x]=center;
    if(chk[pa[x]]==chk[x]){
        int p=pa[x];
        do ++ans,p=pa[p]; while(p^pa[x]);
    }else if(!chk[pa[x]])dfs(pa[x]);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>N;
    for(int i=1;i<=N;i++)cin>>pa[i];
    for(int i=1;i<=N;i++)if(!chk[i])++center,dfs(i);
    cout<<ans<<endl;
}