[規格]1707二分図C++(BFS、DFS)

27296 ワード
白駿 テキストリンク
📌白駿1707二分図
https://www.acmicpc.net/problem/1707

前回は隣接行列を使ったことがありますが、今回は隣接表を使いましょう.
今回は訪問の表示をしないで、色を付けます.赤にRED(2)、青にBLUE(3)を加える.
  • の隣接リスト、アクセス記録、ノード数、幹線数を全域に発表します.隣接テーブルはベクトルで作られています.
  • main()はテスト例を入力し、各テスト例はノード数、幹線数、ノード数を入力します.そして、隣接リスト
    • に入れる
    1. DFS
  • アクセスのために1からNまですべて返され、アクセスレコードを持つ
    • DFSのみが返される
  • 最初のアクセスの場合は、アクセスレコードにREDを追加します.
    接続点
  • を探しに行きますが、接続点もアクセスしたことがありませんか?じゃ、ここで条件を決めてあげます.ナビゲーション開始ノードがREDである場合、接続点にBLUEが挿入され、BLUEである場合にREDが挿入される.
  • および要素別アクセス.この操作を繰り返す(戻る)
    • 2. BFS
  • キューを作成し、開始キューでpush
  • キューの一番前の値をコピーし、CUPOP
    • をコピーします.
  • キューの一番前の値はREDですか?隣接リストに接続されているすべてのノードをBLUEに入れる.(BLUEはRED)
  • check()関数を使用して二分図検査を行います.隣接ノードと開始ノードの色が同じである場合、この図X.同じノードがある場合、
    • に戻る.
  • には重要なものもあります.この問題はテストケースがあるため,隣接表とアクセス記録を複数回記入する必要がある.このため、memsetを使用して初期化する必要があります.
    • DFSプール
    #include <iostream>
#include <vector>
#include <string.h>
using namespace std;

#define RED 2
#define BLUE 3

vector<int> vect[20001]; //인접리스트
int visited[20001];      //방문기록
int V, E;

/* DFS 실행 */
void DFS(int start)
{
    //방문안한 점이면 RED
    if (visited[start] == 0)
        visited[start] = RED;

    //연결된 점들 방문
    for (int i = 0; i < vect[start].size(); i++)
    {
        int idx = vect[start][i];
        if (visited[idx] == 0) //방문 안한 점이면
        {
            //요소에 방문기록 남김(색칠하기)
            if (visited[start] == RED)
                visited[idx] = BLUE;
            else if (visited[start] == BLUE)
                visited[idx] = RED;

            //요소별로 방문
            DFS(idx);
        }
    }
}

/* 이분그래프 검사 */
int check()
{
    //인접한 노드와 색이 같으면 이분그래프 X
    for (int i = 1; i <= V; i++)
    {
        //연결된게 자기자신 뿐일 경우엔 size가 0이라서 돌아가지 않는다.
        for (int j = 0; j < vect[i].size(); j++)
        {
            int idx = vect[i][j];
            if (visited[i] == visited[idx]) 
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int T;    //테스트케이스
    int u, v; //노드 담을 변수

    cin >> T;
    while (T--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        
        //빠짐없이 방문하기 위해 1부터 원소 개수까지 다 방문해봄
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
                DFS(i);
        }

        if (check() == 0) //이분그래프인지 검사
            cout << "NO\n";
        else
            cout << "YES\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}
    BFSプール
    #include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define RED 1
#define BLUE 2

vector<int> vect[20001];
int visited[20001];
int V, E;

void BFS(int start)
{
    visited[start] = RED;
    queue<int> q;
    q.push(start);

    while(q.size()!=0) //큐가 빌 때 까지 반복(전체)
    {
        int now = q.front();
        q.pop();
        for(int i=0; i<vect[now].size(); i++)
        {
            if(visited[vect[now][i]] == 0)
            {
                q.push(vect[now][i]);

                if(visited[now] == RED) visited[vect[now][i]] = BLUE;
                else if(visited[now] == BLUE) visited[vect[now][i]] = RED;
            }
        }

    }

}

bool check()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < vect[i].size(); j++)
        {
            if (visited[i] == visited[vect[i][j]])
                return false;
        }
    }
    return true;
}

int main()
{
    int K, u, v;
    cin >> K;

    while (K--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        //빠짐없이 방문하기 위해 노드 개수만큼 BFS 돌려줘야함
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
            {
                BFS(i);
            }
        }

        //이분그래프 검사
        if (check())
            cout << "YES\n";
        else
            cout << "NO\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}
    Programmers-文字列を整数に置き換える(Python)
    JAva 1週目ウサギ作り