💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
最初の行はコンピュータの数を示します.パソコンの数は100以下で、1台あたり1番から順番に番号をつけます.2行目は、ネットワークに直接接続されているコンピュータペアの数を示します.次に、ネットワークに直接接続された各行の1対のコンピュータの番号ペアが与えられる.
🧺しゅつりょく
1番コンピュータがワームウイルスに感染した場合、1番コンピュータを介してワームウイルスに感染したコンピュータの数を1行目に出力する.

🔋サンプルI/O

🔮入力例1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

🔮サンプル出力1

4

💉もんだいぶんせき

🔋ぶんかつ

BFS, DFS

🔋難易度

シルバーIII

💉問題を解く

🔋解法

まず、彼は起点が1だと言ったので、
ドアは0からではなく1から始まるので
接続されているがアクセスされていないすべてのポイントを巡回するだけです.
この部分はbfsで解いたものです
これは再帰関数を書く方法もあればQを書く方法もある.
個人的には貴重な関数にあまり詳しくありませんが、
キューの使い方を書きました.

🔋ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX (101)

//모든 지점을 저장하기 위한 컨테이너
std::vector<int> adj[MAX];

void bfs(int N, int start){
    int ans = 0;
    std::queue<int>q;
    q.push(start); //시작지점 큐에 저장
    std::vector<bool>visit(N + 1, false);
    visit[start] = true; //시작지점 방문함.

    while(!q.empty()){
    	//cur : 현재지점
        int cur = q.front();
        q.pop();

	//현재지점과 연결된 모든지점을 순회
        for(int i = 0;i<adj[cur].size();++i){
            //next : 다음으로 갈 지점
            int next = adj[cur][i];
            
            //만약 이미 방문한 지점이라면 안갈거임..!
            if(visit[next]) continue;
            
            //방문처리
            visit[next] = true;
            q.push(next);
            
            //이것이 답을 연산하는 부분!
            ++ans;
        }
    }

    std::cout << ans;
}

int main(){
    int N, M;
    std::cin >> N >> M;
    for(int i=1;i<=M;++i){
        int a, b;
        std::cin >> a >> b;
        
        //반드시 서로를 가리켜줘야합니다!
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bfs(N, 1);
}

今度の問題は簡単だ
bfsを貼ればいいのに...

💉終了時..。

今回の問題は段階的な問題を克服する際に書かれたものです
気になるところがあればコメントで質問しましょう!