#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> GS;
vector<bool> visited;
int cctvCount = 0;

bool dfs2(int v, int depth)
{
    visited[v] = true;
    const int size = GS[v].size();
    
    if (depth == 0 && size == 0) { ++cctvCount; return true; }
    
    bool isOk = false;
    for (int i = 0; i < size; ++i)
    {
        const int go = GS[v][i];
        if (!visited[go]) if (!dfs2(go, depth + 1)) isOk = true;
    }
    if (isOk)
    {
        ++cctvCount;
        return true;
    }
    return false;
}

/*
https://algospot.com/judge/problem/read/GALLERY
*/
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T-- > 0)
    {
        int G, H;
        cin >> G >> H;
        GS = vector<vector<int>>(G);
        visited = vector<bool>(G, false);
        for (int i = 0; i < H; ++i)
        {
            int u, v;
            cin >> u >> v;
            GS[u].push_back(v);
            GS[v].push_back(u);
        }
        for (int i = 0; i < G; ++i) if (!visited[i]) dfs2(i, 0);
        cout << cctvCount << endl;
        cctvCount = 0;
    }
    return 0;
}

CCTV 설치 문제 푸는 중 막혀서 질문드립니다.

종만북에서 힌트를 얻어 트리의 잎 부터 CCTV 설치 여부를 검사했습니다.

깊이가 0이고 자식이 없으면 노드 1개의 컴포넌트 이므로 무조건 CCTV를 설치하고

dfs2 반환 값이 0이면 이전 노드에서 CCTV를 설치 안했으므로 현재 노드에서는 무조건 CCTV를 설치 해야 하므로 설치하고

이런 방식으로 설계했습니다만...
저의 실력으로 반례를 찾을 수 없겠네요...

도움을 주시면 감사하겠습니다.

2번째 작성코드(오답 코드)
~~~ c++
int V;
vector> adj;
vector visited;
vector cctv;

int dfs(int v)
{
visited[v] = true;

vector<int> child;
for (int i = 0; i < adj[v].size(); ++i)
{
    const int go = adj[v][i];
    if (!visited[go])
    {
        const int x = dfs(go);
        child.push_back(go);
    }
}
for (auto i : child)
{
    if (!cctv[i])
    {
        cctv[v] = true;
        break;
    }
}
return child.size();

}

int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
int E;
cin >> ::V >> E;
adj = vector>(V);
visited = cctv = vector(V, false);
for (int i = 0; i < E; ++i)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 0; i < V; ++i) if (!visited[i]) if(dfs(i) == 0) cctv[i] = true;
int cctvCount = 0;
for (int i = 0; i < V; ++i) if (cctv[i]) ++cctvCount;
cout << cctvCount << endl;
}
return 0;
}
~~~