그래프에서 음의 사이클 구하기벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다. 플로이드 워셜 알고리즘을 이용한 방법mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다. 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값..
사이클
코드#include using namespace std;int n,m,res,a,b,lst[500002];int find(int x) { if(x == lst[x]) return x; return lst[x] = find(lst[x]);}void merge(int x, int y) { x = find(x); y = find(y); if(x > y) lst[x] = y; else lst[y] = x;}int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i = 0; i > a >> b; if(find(a) != find(b)) { merge(a,b..
