C++ 그래프의 사이클 노드 찾기

사이클 노드 찾기

https://k99812.tistory.com/147

[백준 11400] C++ 단절선 DFS

 

위의 문제의 코드를 바탕으로 코드가 진행된다

 

vector<int> visited, parent, inStack;

int dfs(int start)
{
   visited[start] = ++cnt;
   inStack[start] = true;

   for (const int& next : graph[start])
   {
      if (parent[start] == next) continue;
      if (visited[next])
      {
         if (inStack[next])
         {
            cout << "사이클 노드 : ";
            for (int cur = start; cur != next; cur = parent[cur])
            {
               cout << cur << " ";
            }
            cout << next << "\n";
         }
         continue;
      }
      
   }
   inStack[start] = false;

   return ret;
}

 

DFS가 방문했던 곳을 또 방문하면 사이클이 존재한다 할 수 있다.

하지만 if (visited[next])로만 사이클을 확인하면 방문했던 노드에 또 접근하는 경우에도 

사이클이 발생했다 처리할 수 있다 그래서 inStack 배열을 추가하여 DFS의 경로에 

포함되어 있는 곳을 또 방문한 경우에만 사이클처리를 한다.

 

예제

5 5
1 2
1 3
3 4
4 5
5 3

//출력
사이클 노드 : 5 4 3

7 8
1 4
4 5
5 1
1 6
6 7
2 7
7 3
2 3

//출력
사이클 노드 : 5 4 1
사이클 노드 : 3 2 7

 

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int v, e, cnt;
vector<int> visited, parent, inStack;
vector<vector<int>> graph;
vector<pair<int, int>> bridge;

int dfs(int start)
{
	visited[start] = ++cnt;
	int ret = visited[start];
	inStack[start] = true;

	for (const int& next : graph[start])
	{
		if (parent[start] == next) continue;
		if (visited[next])
		{
			if (inStack[next])
			{
				cout << "사이클 노드 : ";
				for (int cur = start; cur != next; cur = parent[cur])
				{
					cout << cur << " ";
				}
				cout << next << "\n";
			}

			ret = min(ret, visited[next]);
			continue;
		}
		
		parent[next] = start;
		int low = dfs(next);
		ret = min(ret, low);

		if (low > visited[start])
		{
			bridge.push_back({ min(start, next), max(start, next) });
		}
	}
	inStack[start] = false;

	return ret;
}

int main()
{
	cin >> v >> e;

	visited = parent = inStack = vector<int>(v + 1);
	graph = vector<vector<int>>(v + 1);

	for (int i = 0; i < e; i++)
	{
		int from, to;
		cin >> from >> to;

		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	for (int i = 1; i <= v; i++)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}

	sort(bridge.begin(), bridge.end());

	cout << bridge.size() << "\n";
	for (const pair<int, int>& i : bridge)
	{
		cout << i.first << " " << i.second << "\n";
	}

	return 0;
}