백준 17241 (C++) Pineapple Advertising

최초 업로드: 2025-10-03 06:58:02

최근 수정 시간: 2025-10-03 06:58:02

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] Pineapple Advertising

[문제 링크](https://www.acmicpc.net/problem/17241)

## 문제 설명

병찬이는 파인애플을 매우 좋아하며, 특히 파인애플 피자를 매우 좋아한다. 병찬이는 파인애플 피자의 멋짐을 설파하기 위해 한 마을에 파인애플 피자를 광고를 하려고 한다.

이 마을은 총 N개의 집이 있고, 이 N개의 집은 모두 파인애플 피자를 싫어한다. 그 리고 이 마을에는 M개의 길이 있고, 각 길은 특정 두 집을 연결하고 있다. 길의 구성에 따라, 어떤 집은 어떠한 길과도 연결되어 있지 않을 수 있다. 병찬이는 파인애플 피자를 특정 집에 전해줄 수 있다. 그러면 맛있는 파인애플 피자의 냄새로 인해 파인애플 피자를 전달받은 집과, 그 집과 길로 직접 연결된 집들은 파인애플 피자를 좋아하게 된다.

병찬이는 이 마을에 있는 집 중에 Q개의 집에 파인애플 피자를 전해주려고 한다. 물론 한번 피자를 전해준 집에 다시 피자를 전해줄 수 있다. 이 때, 첫 번째 집부터 Q번째 집까지 피자를 배달할 때마다 얼마나 많은 수의 집이 파인애플 피자를 좋아하게 되었는지를 알고 싶다. 병찬이를 도와서 얼마나 많은 집이 파인애플 피자를 좋아하게 되었는지 구해보자.

## 입력

첫 줄에 N, M, Q가 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ M ≤ 1,000,000)

두 번째 줄부터 M + 1번째 줄까지 ai, bi가 주어진다.(1 ≤ ai, bi ≤ N) 이는 집 ai와 집 bi가 길로 연결되어 있다는 것을 의미한다.

그 뒤 Q(1 ≤ Q ≤ 200,000)개의 줄에 걸쳐 피자를 전달할 집의 번호 ni가 주어진다.

## 출력

Q개의 정수를 출력한다. i번째 정수는 병찬이가 집 ni에 파인애플 피자를 주었을 때, 새로이 파인애플 피자를 좋아하게 된 집의 개수를 의미한다.

이미 파인애플 피자를 좋아하고 있는 집은 새로이 파인애플 피자를 좋아하게 된 것 으로 취급하지 않는다.

## 풀이
탐색을 시작하는 정점과 직접 이어진 정점을 간선을 지우면서 방문 처리하면 시간 안에 돕니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 200'001;

bool visited[MAX];
vector<vector<int>> conn(MAX);

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    while(m--) {
        int a, b; cin >> a >> b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }

while(q--) {
        int cur; cin >> cur;

int cnt = !visited[cur];
 visited[cur]=true;
 for(int next:conn[cur]) {
 if(!visited[next]) {
 cnt++;
 visited[next]=true;
 }
 }
 conn[cur].clear();
 cout << cnt << '\n';
 }
}
```