old_Math/Cycle_Decomposition.cpp

• View this file on GitHub
• Last update: 2022-07-19 22:14:43+09:00

Code

vector<vector<int>> cycle_decomposition(vector<int> &P){
	int N = P.size();
	vector<bool> used(N, false);
	vector<vector<int>> ans;
	for (int i = N - 1; i >= 0; i--){
		if (used[i]) continue;
		vector<int> C;
		C.push_back(i);
		while (C.front() != P[C.back()]){
			C.push_back(P[C.back()]);
			used[C.back()] = true;
		}
	ans.push_back(C);
	}
	return ans;
}

#line 1 "old_Math/Cycle_Decomposition.cpp"
vector<vector<int>> cycle_decomposition(vector<int> &P){
	int N = P.size();
	vector<bool> used(N, false);
	vector<vector<int>> ans;
	for (int i = N - 1; i >= 0; i--){
		if (used[i]) continue;
		vector<int> C;
		C.push_back(i);
		while (C.front() != P[C.back()]){
			C.push_back(P[C.back()]);
			used[C.back()] = true;
		}
	ans.push_back(C);
	}
	return ans;
}

Back to top page