글 읽기 - 반례가 혹시 있을까요..?

khj0426 1년 전 0

예제 입출력은 맞는데 반례나 틀린부분을 못찾겠네요..

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<char> graph[30];
int n,m;
bool visited[30];
int cnt = 0;

void dfs(char start){
    if(visited[start-'A']){
        return;
    }
    visited[start-'A'] = true;
    for(int i = 0;i<graph[start-'A'].size();i++){
        char c = graph[start-'A'][i];

        if(visited[c-'A'] == false){
            cnt++;
            dfs(c);
        }
    }
}

 
void input(){
    cin >> n >> m;
 
    for(int i = 0;i<m;i++){
        char a,b;
        cin >> a >> b;
        graph[a-'A'].push_back(b);
    }
    

    int k;
    cin >> k;
    for(int i = 0;i<k;i++){
        char produce;
        cin >> produce;
        visited[produce-'A'] = true;
    }
 
 
}
 
int main(void){
    input();
    dfs('A');
    
    cout << cnt;
}

sr3gm 1년 전 0

꼭 A가 시작이라는 보장은없습니다

psmdc0714 1년 전 0

마약의 원산지(루트 노드)가 무조건 A라는 말은 없습니다. A가 아니라 B, C, Z같은 친구들이 누군가에게 마약을 공급받는 것이 아니라면(자신들을 연결하는 부모 노드가 없다면) 얘네들도 마약 원산지가 될 수 있습니다. 그러니까 A가 무조건 원산지인 게 아니라, B가 오히려 A에게 마약을 공급하는 원산지일 수 있다는 말입니다.

또한 마약 원산지가 하나가 아닐 수 있습니다. A와 B가 동시에 마약 원산지일 수도 있습니다. 특히 마약 원산지(루트 노드)가 여러 개인데 그 루트 노드들에서 이어지는 그래프가 하나가 아니라면, 원산지 하나만 탐색을 돌릴 경우 다른 원산지에서 이어지는 공급책들은 카운트가 되지 않습니다.

반례 1
6 4
A C
A D
B E
B F
1 A
-
출력 : 2

반례 2
9 8
A C
A D
B E
B F
D G
E G
G H
G I
2 A D
-
출력 : 5

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 혹시 있을까요..?

khj0426 1년 전 0

sr3gm 1년 전 0

psmdc0714 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말