백준 10451 순열 사이클

2020. 9. 7. 22:48·알고리즘/BOJ

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>
using namespace std;

int ar[1001], tc, n, cnt;
bool vis[1001];

void dfs(int cur) {
	if (vis[cur]) return;
	vis[cur] = true;
	dfs(ar[cur]);
}

int main() {
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> ar[i];
		fill(vis, vis + 1001, false); //돌 때마다 초기화
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) { //방문하지 않았다면
				dfs(i); cnt++; //한 사이클이 다 될때까지 dfs
			}
		}
		cout << cnt << '\n'; cnt = 0;
	}
}

 

 

 

'알고리즘 > BOJ' 카테고리의 다른 글

백준 4963 섬의 개수  (0) 2020.09.09
백준 2331 반복수열  (0) 2020.09.08
백준 13305 주유소  (0) 2020.09.07
백준 2981 검문  (0) 2020.09.07
백준 12865 평범한 배낭  (0) 2020.09.07
'알고리즘/BOJ' 카테고리의 다른 글
  • 백준 4963 섬의 개수
  • 백준 2331 반복수열
  • 백준 13305 주유소
  • 백준 2981 검문
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    행렬 제곱
    다익스트라
    dp
    트리
    시뮬레이션
    냅색
    크루스칼
    조합
    프로그래머스
    이분탐색
    MST
    BFS
    GREEDY
    구현
    팰린드롬
    이분 탐색
    분할 정복
    dfs
    피사노 주기
    BOJ
    코딩테스트 연습
    우선순위 큐
    완전탐색
    유니온 파인드
    소수
    SWEA
    완전 탐색
    피보나치 수
    큐
    알고리즘
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
백준 10451 순열 사이클
상단으로

티스토리툴바