글 읽기 - c++ 반례좀 찾아주세요 ㅠㅠㅠㅠ

toto6599 5년 전 0

ㅇ예제는 잘 되는 것 같은데 반례좀 알 수 있을까요ㅠㅠㅠ

#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
void BFS(std::vector<std::vector<int>>&, int, int, int);
void DFS(std::vector<std::vector<int>>&, int, int, int);
int main(){
  int Nnode, Nedge, startNode;
  std::cin>>Nnode;
  std::cin>>Nedge;
  std::cin>>startNode;
  std::vector<std::vector<int>> mat(Nnode);
  for (int i =0;i<Nnode;i++){
    mat[i].reserve(Nnode);
  }
  for (int i=0; i<Nedge; i++){
    int a,b;
    std::cin>>a>>b;
    mat[a-1].push_back(b-1);
    mat[b-1].push_back(a-1);
  }
  for (int i=0; i<Nnode; i++){
    sort(mat[i].begin(), mat[i].end());
  }
  BFS(mat, Nnode, Nedge, startNode);
  DFS(mat, Nnode, Nedge, startNode);
  return 0;
}
void DFS(std::vector<std::vector<int>>& mat, int N, int M, int startNode){
  int* chk = new int[M];
  int cnt = 0;
  std::memset(chk, 0, M*sizeof(int));
  std::stack<int> _stack;

  _stack.push(startNode-1);
  chk[startNode-1] = 1;
  std::cout<<startNode<<' ';
  cnt++;
  int flag = 1;
  while (cnt < N && !_stack.empty()){
    if (!flag) _stack.pop();
    int node = _stack.top();
    flag = 0;
    for (int i =0 ; i<mat[node].size();i++){
      if (chk[mat[node][i]]==0){
        chk[mat[node][i]] =1;
        _stack.push(mat[node][i]);
        flag = 1;
        std::cout<<mat[node][i]+1<<' '';
        cnt++;
        break;
      }
    }
  }
  std::cout<<"end";
}
void BFS(std::vector<std::vector<int>>& mat, int N, int M, int startNode){
  int* chk = new int[M];
  std::memset(chk, 0, M*sizeof(int));
  std::queue<int> _queue;

  _queue.push(startNode-1);
  chk[startNode-1]=1;
  while (!_queue.empty()){
    int node = _queue.front();
    _queue.pop();
    std::cout<<node+1<<" ";
    for (int i = 0; i<mat[node].size();i++){
      if (chk[mat[node][i]] == 0) {
        chk[mat[node][i]] = 1;
        _queue.push(mat[node][i]);
      }
    }

  }
  std::cout<<'\n';
}

djm03178 5년 전 1

아무거나 입력해도 DFS 끝에서 "end" 라는 문자열을 출력하기 때문에 무조건 틀립니다. DFS 이후 개행도 없습니다.

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

문제

문제

출처

ICPC

c++ 반례좀 찾아주세요 ㅠㅠㅠㅠ

toto6599 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말