윤만석

문제 Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country. ACM++ has therefore decided to connect the netwo..

문제 선인장이란 양방향 그래프의 일종인데, 각 정점에 대해 자기 자신으로 돌아오는 경로(단순 사이클)가 하나 이하인 그래프이다. 주어진 그래프가 선인장일까? 아닐까? 입력 첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정수 x,y (1 ≤ x,y ≤ N,x ≠ y)가 공백으로 구분되어 주어진다. 주어진 간선은 중복되지 않으며, 임의의 두 정점에 대해 경로가 존재한다. 출력 주어진 그래프가 선인장이면 "Cactus" 를 아니라면 "Not cactus" 를 출력한다. 선인장 그래프 문제입니다. 단순 사이클이란 한 사이클에서 같은 정점을 방문하지 않..

문제 그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오. 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 입력 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다...

문제 그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오. 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다. 입력 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. 정점은 1부터 V까지 번호가 매겨져 있다. 출력 첫째 줄에 단..