ネットワークC++

問題の説明

ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.

せいげんじょうけん

コンピュータの個数nは、1又は複数の200以下の自然数である.
各コンピュータは0からn−1までの整数で表される.
i番コンピュータがj番コンピュータに接続されている場合、コンピュータ[i][j]は1として表される.
コンピュータ[i][i]は常に1.

に答える

この問題はdfsでc++で類似のタイプの記憶を解き、c++で書き直した.1つのネットワークに接続されているすべてのコンピュータを0に変更し、ネットワーク内のすべてのコンピュータを0にすると、答えに1を加える形で行います.
すべてのコンピュータ[i][i]=1自体が1であるため、チェックしたコンピュータは0に変更され、まだチェックしていない場合は1に分割される.整理するなら.

n回繰り返し、検索コンピュータ

コンピュータに接続されているすべてのコンピュータ[i][i]=0.

接続されていないコンピュータはtrueを返します.

#include <string>
#include <vector>

using namespace std;

bool dfs(vector<vector<int>>& computers , int n)
{
    if(computers[n][n] == 0)
        return false;
    computers[n][n] = 0;
    
    for (int i = 0; i< computers.size(); i++)
    {
        if (computers[n][i])
            dfs(computers,i);
    }
    return true;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i = 0 ; i < n ; i ++)
    {
        if(computers[i][i] && dfs(computers, i))
            answer ++;
    }
    return answer;
}