사이클 판단

들어올때 양쪽 다 아직 없으면 vector 생성 후 넣기 한쪽만 있으면 해당 vector에 추가 한쪽씩 따로 있으면 연결 양쪽 다 있으면 cycle

점이 500,000개 입력이 1,000,000줄인데 이걸 어캐함

id로 처리?

vector 점 개수만큼 넣어놓고 vector[i]에 id 저장

id -1이면 아직 안 없는거 id가 있으면 넣기

n1, n2 들어오면

if vector[n1] != -1 && vector[n1] == vector[n2]: cout << 현재 진행 << endl; return;

else if vector[n1] == -1 && vector[n2] == -1: vector[n1] = id vector[n2] = id id++;

else if vector[n1] != -1 && vector[n2] != -1: int target_id = vector[n2]; for i=0->N: if vector[i] == target_id: vector[i] = vector[n1]

else if vector[n1] != -1 && vector[n2] == -1: vector[n2] = vector[n1]

else if vector[n2] != -1 && vector[n1] == -1: vector[n1] = vector[n2]

나머지는 다 괜찮은데 연결할때 복잡도가 좀 에러인데

다 통과하는데 시간초과 뜸

찾아보니까 Union_Find라는거로 풀 수 있다 함 id 기준이 아니라 root를 지정해서 다른 root면 같은 root로 지정, 같은 root면 cycle 초기에는 모두 자기자신 root 가짐. union시 자기 자신을 root로 가질때까지 올라가면서 변경.

초기 0 1 2 3 4

1 3 0 3 2 3 4

2 3 0 3 3 3 4

1 2 0 3 3 3 4 -> find, 3