순열 사이클 분할 w/ 값 압축

cycledecomp.cpp

#include<iostream>
#include<vector>
#include<map>
#include<functional>
using namespace std;
using ll=long long;

template<class T>
vector<vector<T>> decomp(vector<T> vec)
{
	map<T,ll> cmp; map<ll,T> decmp;
	int t=0;
	for(ll i:vec)cmp[i];
	for(auto&[i,j]:cmp){j=t;decmp[t++]=i;}
	bool visit[size(vec)];
	for(bool&b:visit)b=0;
	function<void(vector<ll>&,int)>
	dfs=[&](vector<ll>&res,int idx)->void
	{
		if(visit[idx])return;
		res.push_back(vec[idx]);
		visit[idx]=1;
		dfs(res,vec[idx]);
	};
	
	for(T&i:vec)i=cmp[i];
	
	vector<vector<T>> ans;
	for(int i=0;i<size(vec);i++)
	{
		vector<T>tmp;
		if(!visit[i])
		{
			dfs(tmp,i);
			for(T&i:tmp)i=decmp[i];
			ans.push_back(tmp);
		}
	}
	return ans;
}

int main()
{
	int n;cin>>n;
	vector<ll>vec(n);
	for(ll&i:vec)cin>>i;
	auto dec=decomp(vec);
}