[DATASTRUCTURE] DFS로 Cycle 확인하기

DFS는 stack BFS는 Queue를 이용하여 구현한다.

DFS에서 visit가 2번 이상된 노드가 있다면

그것은 cycle이 생겼다는 의미이다.

#include <iostream> #include <vector> #include <stack> #include <fstream> using namespace std; stack<int> storage; vector<int> visit; vector<vector<int>> graph; int graph_count; void dfs() { storage.push(1); while (!storage.empty()) { int index = storage.top(); visit[index]++; if (visit[index] >= 2) return; storage.pop(); for (int j = 0; j < graph[index].size(); j++) { if(visit[graph[index][j]]==0) storage.push(graph[index][j]); } } } int main() { ifstream fcin; fcin.open("Kim's_Family_input.txt"); int for_count; fcin >> for_count; int edge_count,start_index,end_index; while (for_count--) { fcin >> graph_count>> edge_count; graph = vector<vector<int>>(graph_count+1); visit = vector<int>(graph_count + 1, 0); while (edge_count--) { fcin >> start_index >> end_index; graph[start_index].push_back(end_index); graph[end_index].push_back(start_index); } while (!storage.empty()) storage.pop(); dfs(); if (storage.empty()) cout << 1 << endl; else cout << 0 << endl; } system("pause"); }