PS 일지

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 요약 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 더보기 이분 그래프(Bipartite Graph)? 그래프의 정점의 집합을 둘로 분할했을 때, 각 집합에 속한 정점끼리 서로 인접하지 않게 할 수 있는 그래프이다. 접근 이분 그래프를 모르는 상태에서 문제를 접하다보니 구현에 실수가 조금 있었다. 양방향 그래프를 입력 받고, visit배열을 통해 방문 여부를 확인하며 평범한 DFS를 구..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 요약 $N$개의 정점과 $N$개의 간선으로 이루어진 방향 그래프가 주어졌을 때, 그래프에서 사이클을 이루지 않는 정점의 개수를 구하는 문제이다. 접근 DFS를 수행하며 사이클을 찾고, 사이클을 이루는 정점의 수를 파악해야 한다. 사이클 찾기 정점이 최대 10만 개이기 때문에 방문 여부를 저장하는 배열 visit을 선언하고, 반복문을 통해 방문하지 않은 점에 대해 1번 정점부터 N번 정점까지 DFS..