[백준] 순열 사이클 - 10451
링크
문제
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<ArrayList<Integer>> list;
static boolean check[];
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
ArrayList<Integer> result=new ArrayList<Integer>();
for(int tc=0; tc<t; tc++)
{
int count=0;
int num=Integer.parseInt(br.readLine());
check=new boolean[num+1];
list=new ArrayList<>();
for(int i=0; i<=num; i++)
list.add(new ArrayList());
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=1; i<=num; i++)
{
int number=Integer.parseInt(st.nextToken());
list.get(i).add(number);
}
for(int i=1; i<list.size(); i++)
{
if(!check[i])
{
DFS(i);
count++;
}
}
result.add(count);
}
for(int answer : result)
System.out.println(answer);
}
public static void DFS(int num)
{
if(!check[num])
check[num]=true;
for(int i=0; i<list.get(num).size(); i++)
{
int next=list.get(num).get(i);
if(!check[next])
{
check[next]=true;
DFS(next);
}
}
}
}
Author And Source
이 문제에 관하여([백준] 순열 사이클 - 10451), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@ehdcks3421/백준-순열-사이클-10451
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<ArrayList<Integer>> list;
static boolean check[];
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
ArrayList<Integer> result=new ArrayList<Integer>();
for(int tc=0; tc<t; tc++)
{
int count=0;
int num=Integer.parseInt(br.readLine());
check=new boolean[num+1];
list=new ArrayList<>();
for(int i=0; i<=num; i++)
list.add(new ArrayList());
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=1; i<=num; i++)
{
int number=Integer.parseInt(st.nextToken());
list.get(i).add(number);
}
for(int i=1; i<list.size(); i++)
{
if(!check[i])
{
DFS(i);
count++;
}
}
result.add(count);
}
for(int answer : result)
System.out.println(answer);
}
public static void DFS(int num)
{
if(!check[num])
check[num]=true;
for(int i=0; i<list.get(num).size(); i++)
{
int next=list.get(num).get(i);
if(!check[next])
{
check[next]=true;
DFS(next);
}
}
}
}
Author And Source
이 문제에 관하여([백준] 순열 사이클 - 10451), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ehdcks3421/백준-순열-사이클-10451저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)