アルゴリズム::白準::DFS::1707:二分図

11056 ワード
テキストリンク

質問する



質問へのアクセス


この問題の詳細はアルゴリズム::白準::DFS::1707::二分図(velog.io)にあります.今回はもっと効果的に同じ問題を解決します.

問題を理解する

  • 問題条件には記載されていないが、本問題の二分図は無方向図である.
  • 二分図の特徴によれば、任意の頂点から幹線に沿って別の頂点に移動する際に、到達した頂点を始点と反対のグループに入れる.(A → B → A → B...)
  • いずれかの頂点から別の頂点に移動した場合、その頂点がアクセスされたポイントであり、同じグループである場合、二分図形条件に違反します.

    • 解法

  • 任意の点ですべての点にナビゲートするにはDFSまたはBFSを使用する必要があることに気づいた.
    いずれの方法を使用しても、この問題は関係ありません.
  • 私にとっては任意の頂点を基準に幹線に沿って奥行きを移動する画像に慣れているのでDFSを使用しました.
  • 0未訪問、1乙組A、2乙組B仮定state[]配列宣言.
  • 任意頂点のstate可xの場合、次の頂点のstateはい3-x(1 → 2, 2 → 1)
  • この時点で接続されている次の頂点は既にアクセスされている点stateもしそうであれば二分図ではないと判断できる.

    • コード#コード#

    #include <iostream>
#include <vector>
using namespace std;

bool ans;
int K, V, E, state[20001];
vector<int> graph[20001];

void dfs(int cv, int s) {
	state[cv] = s;
	for (int nv : graph[cv]) {
		// 방문하지 않은 정점에 대해 반대 그룹 표시
		if (!state[nv]) dfs(nv, 3 - s);
		// 방문된 정점에 대해 같은 그룹 여부 확인
		if (state[nv] == state[cv]) { ans = true; break; }
	}
}

void solve() {
    // 모든 정점에 대해 dfs를 수행함.
	for (int i = 1; i <= V; ++i) {
		if (!state[i]) dfs(i, 1);
		if (ans) break;	// 이분그래프가 아닌 경우
	}
}

void clear() {
	ans = false;
	fill(state, state + V + 1, false);
	for (int i = 1; i <= V; ++i) graph[i].clear();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> K;
	while (K--){
		cin >> V >> E;
		int sv, ev;
		for (int i = 0; i < E; ++i) {
			cin >> sv >> ev;
            // 무방향 그래프
			graph[sv].push_back(ev);
			graph[ev].push_back(sv);
		}
		solve();
		ans ? cout << "NO\n" : cout << "YES\n";
		clear();	// 다음 loop를 위한 초기화 과정
	}
}

    結果


    カスタムActivityタイトルバー(Title bar)とフォーム表示状態操作(requestWindowFeature()の適用)
    Activityを破棄せずに戻るキーを書き換える