[C++/백준]10451 순열 사이클

이소진·2021년 1월 21일
0

#10451 순열 사이클
https://www.acmicpc.net/problem/10451

📝문제 포인트

단방향 그래프이다. map[i].push_back(a); map[a].push_back(i);를 둘 다 해주지 않아도 된다는 말이다 !!!
연결요소 개수를 구하는 문제(https://www.acmicpc.net/problem/11724)를 풀었다면 어렵지 않게 풀린다

✍코드

#include <iostream>
#include <vector>
#include <string.h>
#define MAX 1001
using namespace std;

int n, m, a;
vector<int>map[MAX];
bool visited[MAX];

void dfs(int v) {
	visited[v] = true;
	for (int i = 0; i < map[v].size(); i++) {
		if (!visited[map[v][i]]) {
			dfs(map[v][i]);
		}
	}
}

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

	int T,count=0;
	cin >> T;

	for(int t=0;t<T;t++) {
		memset(visited, 0, sizeof(visited));
		cin >> m;
		for (int i = 1; i <= m; i++) map[i].clear();
		for (int i = 1; i <=m; i++) {
			cin >> a;
			map[i].push_back(a);
		}

		count = 0;
		for (int i = 1; i <= m; i++) {
			if (!visited[i]) {
				dfs(i);
				count++;
			}
		}
		cout << count<<'\n';
	}
	
}
profile
webFront / Flutter / iOS 😉

0개의 댓글