[21604][伯俊/BOJ]10451番シーケンス周期

991 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する



にゅうしゅつりょく



に答える


シーケンス図内にどれだけのシーケンス周期があるかの問題を求めます.
  • DFSを用いてすべての始点から探索を行った.
  • visでアクセスしたかどうかを確認し、アクセスしていない場合はcnt++を使用して探索します.
  • の最終cnt値は、シーケンスサイクルの個数である.

    • コード#コード#

    #include <bits/stdc++.h>
using namespace std;
#define SIZE 1002

int board[SIZE];
bool vis[SIZE];

void DFS(int V)
{
	vis[V] = 1;
	int nxt = board[V];

	if (!vis[nxt])
		DFS(nxt);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		int n, cnt = 0;
		cin >> n;

		for (int i = 1; i <= n; ++i)
			cin >> board[i];
		
		for (int i = 1; i <= n; ++i)
		{
			if (!vis[i])
			{
				DFS(i);
				cnt++;
			}
		}
		cout << cnt << '\n';
		fill(vis, vis + SIZE, 0);
	}
}
    HDu 1698セグメント変更値
    [DP/白駿1932]整数三角形