[C++] 백준 10451번 순열 사이클

사이클을 확인하는 문제입니다.

DFS를 통해서 각 노드에서 이어진 노드를 전부 방문처리를 해주었습니다.
이어진 노드끼리는 방문처리 과정에서 같은 노드라고 체크해주었습니다.
ex) 1, 3, 4 싸이클,     2, 5 싸이클
visit[1] = 1
visit[3] = 1
visit[4] = 1

visit[2] = 2
visit[5] = 2

위와 같이 각 싸이클에 해당 넘버를 지정해서 체크해주고
최종적으로 넘버를 통해서 싸이클이 몇개인지 확인했습니다.

 

      

      

      

    
    

      <c++ />
    
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

int ts;
int n;
int num;
int c = 1;
int cycle;
int visit[1010];
vector<vector<int> > v;

int DFS(int cur)
{
	int r = 1;
	for (int i = 0; i < v[cur].size(); ++i) {
		if (visit[cur] == 0) {
			visit[cur] = c;
			r = min(r, DFS(v[cur][i]));
		}
		else if (visit[cur] == c) {
			return 1;
		}
		else {
			return -1;
		}
	}
	return r;
}

int main(int argc, char* argv[])
{
	cin >> ts;

	while (ts--) {
		cin >> n;

		c = 1;
		v.clear();
		v.resize(n + 1);
		memset(visit, 0, sizeof(visit));
		
		for (int i = 1; i <= n; ++i) {
			cin >> num;
			v[i].push_back(num);
		}

		for (int i = 1; i < n + 1; ++i) {
			cycle = 0;
			if (visit[i] == 0) {
				cycle = max(cycle, DFS(i));
			}
			c += cycle;
		}

		cout << c - 1 << endl;
	}

	return 0;
}