BFS、DFSプール(標準1707)

質問する
グラフィック頂点の集合を2つの集合に分割し、各集合に属する頂点間を隣接しない集合に分割できる場合、これらのグラフィックを特に二分図(Bipartte Graph)と呼ぶ.
グラフィックが入力されると、そのグラフィックが二分グラフィックであるか否かを判別するプログラムを作成します.
入力
入力は複数のテストケースからなり、第1行はテストケースの個数Kを与える.各試験例の第1行において、図形頂点の個数Vと幹線の個数Eは、スペースを隔てて順次与えられる.各頂点は1からVの順に番号付けされます.次に、2行目から、E行の間に幹線に関する情報が与えられ、各行に隣接する2つの頂点の番号u,v(u≠v)がスペースを隔てて与えられる.
しゅつりょく
K行に入力された図形が二分図であれば、YESまたはNOの順に出力される.
制限
2 ≤ K ≤ 5
1 ≤ V ≤ 20,000
1 ≤ E ≤ 200,000
解答方法
このグラフが何なのかを知ってこそ答えられる問題だ.隣接する頂点の間に異なる色で塗りつぶされ、すべての頂点に2つの色のグラフィックしか塗りつぶされません.
すなわち,図形中のすべての頂点が2つのグループに分けられ,異なるグループの頂点が幹線に接続された図形を二分図と呼ぶ.
それが分かれば、通常のBFS、DFSでグラフを巡回し、自分のサブノード(関連付け)を自分とは異なる色に塗ることができます.また、既に塗ってある場合は、そのままスキップします.このように分岐を区切るためにboolで変数を宣言するよりもintで配列変数を宣言し,0の場合はまだこのインデックスにアクセスしていないが,1の場合は赤2の場合は青で行う.このようにBFSやDFSですべてのノードにアクセスした後,自分の隣接するノードの色と自分の色を比較して二分図かどうかを判断すればよい.
コード#コード#

#include<iostream>
#include<queue>

using namespace std;
#define MAX 20000 + 1

#define RED 1
#define BLUE 2


int V,E;



int colored[MAX];
vector<int> vecVer[MAX]; //간선 표현


void Init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void bfs(int start)
{
    queue<int> q;
    q.push(start);
    colored[start] = RED; //RED부터 시작

    int curColor;
    int idx;

    while(!q.empty())
    {
        idx = q.front();
        curColor = colored[idx]; //현재 자신의 색깔을 받아준다.
        q.pop();

        for(int i = 0; i < vecVer[idx].size(); ++i) //자신과 연결되어 있는 모든 간선들을 방문해주기 위한 반복문
        {
            if(colored[vecVer[idx][i]] == 0) //idx 1이라면 1의 모든 자식 객체들의 색깔들을 확인한다.
            {
                if(curColor == RED)
                {
                    colored[vecVer[idx][i]] = BLUE;
                    q.push(vecVer[idx][i]);
                }
                else if(curColor == BLUE)
                {
                    colored[vecVer[idx][i]] = RED;
                    q.push(vecVer[idx][i]);
                }
            }
        }
    }
}

void dfs(int start, int color)
{
    colored[start] = color;
    for(int i = 0; i < vecVer[start].size(); ++i)
    {
        int next = vecVer[start][i];
        
        if(colored[next] == 0)
        {
            dfs(next, 3 - color);
        }
    }
}


bool Bipartitegraph()
{
    for(int i = 1; i <= V; ++i)
    {
        for(int j = 0; j < vecVer[i].size(); ++j)
        {
            if(colored[i] == colored[vecVer[i][j]])
            {
                return false;
            }
        }
    }

    return true;

}

int main()
{

    Init();
    
    int K;
    cin >> K;

    
    int from, to;


    while(K--)
    {
        cin >> V >> E;

        for(int i = 1; i <= V; ++i)
        {
            colored[i] = 0;
            vecVer[i].clear();
        }

        for(int i = 0; i < E; ++i)
        {
            cin >> from >> to;
            vecVer[from].push_back(to);
            vecVer[to].push_back(from);
        }

        for(int i = 1; i <= V; ++i)
        {
            if(colored[i] == 0)
            {
                dfs(i,1); //기본 처음 시작은 RED로 고정
            }
        }

        if(Bipartitegraph())
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';

    }
    return 0;
}