방향성그래프는 정점들(V)과 방향을 표현하는 간선들(E)로 이루어져 있다.

간선(u,v)는 u에서 v로의 방향을 나타낸다. ((v,u)는 반대방향을 의미한다.)

방향성그래프에서 유방향 순환은 아래와 같이 간선들의 순서들로 나타낸다.

(u1, v1),(u2, v2),...,(uk, vk)

여기서 u의 i+1번째와 v의 i번째는 같고, i=1~(k-1)까지 반복된다.

u의 i번째와 u의 j번째가 같지 않으면, 반드시 i와 j도 같지 않다.

이런 조건에서의 유방향 순환은 간단하다.

강연결 유방향 그래프(strongly connected directed graph)에서는,

몇 개의 유방향 그래프의 모든 정점들은 u와 v의 모든 쌍으로 되어 있고, u와 v모두를 방문하게 된다.

유방향 그래프가 강연결이고 각 간선이 어떤 단순 유방향 순환에 정확히 한 번씩 포함 되는 경우에만 opunita(선인장)이 된다.

첫 번째 그래프는 opunita지만, 두 번째의 경우 간선 (0,1) 와 같은 경우 때문에 opunita가 되지 않는다.

선인장 이름의 유래는 나무와 같은 식으로,

여러 개의 단순 순환들이 연결되어 구조를 이루는데, 이것이 흡사 선인장과 같아서 선인장이란 이름이 붙었다.

주어진 유방향 그래프가 opunita가 되는지를 판단해라. 그래프는 수천개의 정점들을 가질 수 있다.

선인장 timer 1s memory 128MB

선인장 1s 128MB