• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

2-S fill과 memset 질문 있습니다.

22.01.07 09:17 작성 조회수 160

1

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;



int n, m, a, b;
int _max = numeric_limits<int>::min();
int virus[10002];
vector<int> adjList[10002];
bool visited[10002];

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int DFS(int v) {
    visited[v] = 1;
    int infection = 1;
    for (auto adjV : adjList[v]) {
        if (visited[adjV]) continue;
        infection += DFS(adjV);
    }
    return infection;
}

int main() {
    fastIO();

    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        adjList[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        //memset(visited, 0, sizeof(visited));
        fill(visited, visited + 10000, 0);
        virus[i] = DFS(i);
        _max = max(_max, virus[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (virus[i] == _max) {
            cout << i << ' ';
        }
    }

    return EXIT_SUCCESS;
}

완탐을 DFS로 변경하여 풀었는데, fill()을 사용하여 0으로 초기화하면 계속 틀렸다 채점돼서 풀이 참고하여 memset()으로 변경하니 정답으로 채점됩니다.

똑같이 0으로 초기화 하는 것 아닌가요..?

답변 2

·

답변을 작성해보세요.

2

찬비님의 프로필

찬비

질문자

2022.01.07

visited[10000] 까지 초기화 하려면 visited + 10001이라고 했어야 했는데 실수 했네요.

해결했습니다. 비슷한 실수 하시는 분들 있을까봐 참고하라고 그냥 두겠습니다.

1

안녕하세요. 찬비님ㅎㅎ

fill 함수의 내부 구현체를 보면 다음과 같이 되어있습니다.

template <class ForwardIterator, class T>

  void fill (ForwardIterator first, ForwardIterator last, const T& val)

{

  while (first != last) {

    *first = val;

    ++first;

  }

 

}

 

Forward iterators to the initial and final positions in a sequence of elements that support being assigned a value of type T. The range filled is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

또한 지금 보시면 범위를 [first,last) 로잡아야 한다고 되어있구요. 

이렇기 때문에 만약 10002로 잡았다면 visited + 10002가 되어야 합니다. 

또 질문사항있으시면 언제든 말씀 부탁드립니다. 

감사합니다. 

 

강사 큰돌 올림.