알고리즘 공부

백준 순열 사이클

컴퓨터과학 2023. 7. 13. 22:16

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

 

10451번: 순열 사이클

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3

www.acmicpc.net

너무 쉽네여

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
using namespace std;

void Prints(vector<vector<char>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
struct Point {
	int s;
	int e;
	int cnt;
};
struct Data {
	int index;
	int cnt;

};

int main() {

	//1~n
	//3,2,7,8,1,4,5,6
	int T;
	cin >> T;
	
	for (int z = 0; z < T; z++) {
		int n;
		cin >> n;
		vector<Point>maps;
		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			Point p;
			p.s = i + 1;
			p.e = tmp;
			maps.push_back(p);
		}
		vector<bool>bCheck(n, false);
		queue<int>q;
		
		int count = 0;
		for (int k = 0; k < n; k++) {
			if (bCheck[k] == false) {
				count++;

				q.push(maps[k].e);
				bCheck[k] = true;
				
				while (!q.empty()) {
					int start = q.front();
					q.pop();
					for (int i = 0; i < n; i++) {
						if (start == maps[i].s&&bCheck[maps[i].s - 1] == false) {
							q.push(maps[i].e);
							bCheck[maps[i].s - 1] = true;

						}
					}
				}
			}
			
		
		}
		cout << count << endl;

	}
	
	

	return 0;
}