D - New Friends (atcoder.jp) D - New Friends AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제를 요약하자면... 어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면 그러한 경로의 개수를 구하는 문제 예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데, 1 > 2 > 3으로 갈 수 있으므로 1개 2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지..
1. connected component connected component란 다음 두 조건을 모두 만족하는 node의 집합 1) 모든 node가 path로 연결이 가능하다 2) 하나의 node를 추가 했을 때 위 조건을 만족해서는 안된다. 쉽게 생각해서 서로 연결되어 모여있는 집합들이 연결요소다. {9} 하나의 경우도 위 network에서 하나의 연결요소다. 두번째 조건이 무슨 말인지 이해하기 어려운데 {1,2,3,4}의 경우 node 5를 추가하면 {1,2,3,4,5}는 첫번째 조건을 만족하므로 {1,2,3,4}는 연결요소가 아니라는 뜻이다. 2. giant connected component In many networks as the network grows the components get gra..
1. 문제 E - Good Graph (atcoder.jp) E - Good Graph AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 그대로 구현하면 바로 시간초과 당하는데 조금만 생각하면 상당히 간단한 문제가 된다 N개의 정점을 가지고 M개의 간선을 가지는 그래프 G가 주어지는데 모든 i = 1,2,3..,k에 대하여 G에 존재하는 두 정점 $x_{i}, y_{i}$가 서로 연결되어 있지 않다면, G가 good 그래프이다. 이 때, Q개의 query가 주어지는데, 그래프 내의 두 정점 $p_{i}, q_{i..
1. 문제 D - Unicyclic Components (atcoder.jp) D - Unicyclic Components AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 주어진 그래프에서 모든 연결요소가 정점의 개수와 간선의 개수가 같은지 판단하는 문제 2. 풀이 연결요소 하니까 BFS로 찾아볼려고 했는데.. 이게 간선을 관리하기가 만만치 않다 심지어 이 문제는 두 정점 사이 간선이 여러개 있어도 상관없고, 동일한 정점에 간선이 있는 루프도 있다 editorial 피셜로 "One can manage the connect..
1. 연결요소 연결 요소(Connected Component) (velog.io) 연결 요소(Connected Component) 그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유 velog.io 위 그래프가 2개의 그래프로 볼 수도 있지만, 1개의 그래프가 2개의 연결요소를 가진다고 볼 수 있다. 연결요소(connected component)는 해당 요소에 속하는 모든 정점을 연결하는 경로가 있어야하고 또 다른 연결요소에 속한 정점과 연결하는 경로가 없어야한다. 2. 문제 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
