반응형
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
www.acmicpc.net
#include <iostream>
#include <queue>
using namespace std;
int N, M; // 정점 , 간선 갯수
const int MAX = 1000;
int start = 1, cnt = 0 , temp;
int adj[MAX][MAX] = {
0,
};
queue<int> q;
bool flag[MAX];
void DFS(int in){
flag[in] = true;
for(int i =0 ; i<=N ;i++)
{
if(adj[in][i] == 1 && !flag[i])
{
DFS(i);
cnt++;
}
}
}
int main()
{
cin >> N >> M;
int s, e;
for (int i = 0; i < M; i++)
{
cin >> s >> e;
adj[s][e] = 1;
adj[e][s] = 1;
}
DFS(start);
q.push(start);
flag[start] = true;
while (!q.empty())
{
temp = q.front();
q.pop();
for (int i = 0; i <= N; i++)
{
if (adj[temp][i] == 1 && !flag[i])
{
q.push(i);
flag[i] = true;
cnt++;
}
}
}
cout << cnt << endl;
}반응형