[バックアップ]1724接続要素数C++(BFS、DFS)

15957 ワード
白駿 テキストリンク
📌バックエンド11724接続要素数
https://www.acmicpc.net/problem/11724
グラフがすべて接続されているか、途中で切断されている可能性があります.
次から次へと切れて、一つの接続要素になった.
これは、出力に接続要素がいくつあるかの問題です.
接続された要素がある場合、DFS関数は連続的に呼び出されます.また,アクセスレコードの接続要素がなければ終了する.次から次へと切れて一つの接続要素ができた次にmain()を返し、main()の隣接するリスト要素にアクセスレコードがない場合に実行します.
すなわち,main()上でDFSを実行する場合,接続要素の数は+1となる.
BFS関数はキューに移動して空にされる.すなわち,接続されたノードを探索して終了する.これもDFSと同様に、アクセスレコードがなくなると「終了」または「main()」に戻ります.このときmain()上でBFSを実行すると,接続要素の個数は+1となる.

DFSプール

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

vector<int> vect[1001]; //인접리스트
int visited[1001];      //방문기록
int N, M;

/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
    visited[vertex] = 1;
    for (int i = 0; i < vect[vertex].size(); i++) //최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
    {
        int idx = vect[vertex][i];
        if (visited[idx] == 0)
        {
            DFS(idx);
        }
    }
}

int main()
{
    int u, v;
    int cnt = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u); //무방향 그래프이기 때문
    }

    for (int i = 1; i <= N; i++) //빠짐없이 탐색하기 위해
    {
        if (visited[i] == 0)
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

BFSプール

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

vector<int> vect[1001];
int visited[1001];
int N, M;

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

    while (q.size() != 0)
    {
        // start가 아닌 가장 앞의 값에 인근 정점을 push 해줘야함
        int current = q.front();
        q.pop();
        for (int i = 0; i < vect[current].size(); i++)
        {
            if (visited[vect[current][i]] == 0)
            {
                visited[vect[current][i]] = 1; 
                q.push(vect[current][i]);
                //BFS는 재귀가 아니라서 큐에 push 해주는 동시에 방문기록 남겨야함.
            }
        }
    }
}

int main()
{
    int cnt = 0; //연결요소 개수 세는 변수
    int u, v;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u);
    }

    //빠짐없이 탐색하기 위해
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] == 0)
        {
            BFS(i);
            cnt++;
        }
    }
    cout << cnt;
}
CyberPowerのUPSをLinux(Fedora 25)に導入してmuninでグラフ化する
アルゴリズム-KMP文字列マッチングとそのPython実装