白駿9466:Tumpプロジェクト

2259 ワード
DFS cpp テキストリンク
https://www.acmicpc.net/problem/9466

1.近接

  • は1人の学生によって指摘され、それから学生について行われるので、DFSは適切な
    • である.
  • 組の学生を見つけて、全体の人数を除いて、
  • 学生は1人のみを指すため、通常int配列
    • を用いる.
  • 既存のdfsで使用されるアクセス関数は、
    • のままである.
  • 接続要素の問題とは異なり、サイクルは
    • を完了する必要があります.
  • サイクルに属する頂点またはまったく属していない頂点については、done配列で
    • を確認します.
  • cstring.h->memset関数初期化配列

    • 2.その他の反例（問題掲示板を参照）


    1
    7
    2 3 4 2 6 7 5
    正解.

    3.私の回答

    #include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;

int graph[MAX];
bool visited[MAX];
bool done[MAX];
int ret;

void dfs(int x) {
	visited[x] = true;

	if (!visited[graph[x]]) {
		dfs(graph[x]); //다음 노드 실행
	}
	else { //이미 방문했다면 
		if (!done[graph[x]]) { //다음 노드가 끝나지 않았다면
			//cout << "사이클 "<<x<<" ";
			for (int i = graph[x]; i != x; i = graph[i]) { //자기 자신으로 돌아올 때까지 반복문
				//cout << i<<" ";
				ret++;
			}
			ret++;
			//cout << "\n";
		}
	}
	done[x] = true; //모든 확인이 끝났음
	//cout << x << " done 처리 \n";
}

int main() {

	int t;
	cin >> t;

	for (int j = 0; j < t; j++) {
		int n;

		cin >> n;
		ret = 0;
		memset(graph, 0, sizeof(graph));
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));

		for (int i = 1; i <= n; i++) {
			cin >> graph[i];
		}

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) { //기존의 dfs 실행처리
				dfs(i);
			}
		}

		cout << n - ret << "\n";
	}
}
    https://sw-ko.tistory.com/87
    リファレンス

    評価


    ★★★★☆
    失敗する可能性はあるが,dfsはほとんど利用されていない.
    私はpath探索周期を追跡するアルゴリズムを書いたが,効率が低いようだ.
    グラフ問題は既存のdfsをできるだけ維持し,解決策で考えるべきである.
    linux常用コマンド個人メモ
    [functional-js]エラーハンドル