야생가오리

https://www.acmicpc.net/problem/1043 거짓말쟁이가 되기시러각 파티의 참여자를 서로 연결하고, 타고타고 올라갔을때 진실을 아는 사람을 만나는지 안 만나는지를 확인해야 한다. 연결하고 찾는데는 유니온파인드를 사용한다.보자마자 이거다 하고 생각이 안 났다.. 사실 지금도 잘은 모르겠다 첨엔 걍 단순히 진실을 아는 사람이 파티에 섞여있는가를 따지는 문제인가 싶었는데, 같은 사람이 다른 파티에 참여해 다른 사실을 듣는 것 역시 안 된다는 조건 때문에 유니온파인드를 사용해줘야 했다. 우선 유니온파인드 구현은 언제나와 같다.vectorparent;int findParent(int node) { if (parent[node]  입력으로 진실을 아는 사람들이 주어진다. 이 사람들을 kn..

https://www.acmicpc.net/problem/16562 문제 19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람..

https://www.acmicpc.net/problem/4803 문제그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진..

https://www.acmicpc.net/problem/1717 문제초기에 n+1개의 집합 {0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 입력첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다. 출력1로 ..