글 읽기 - dfs 그래프의 요소들 중 최대 크기 찾는 문제, 반례가 뭘까요..?

dohoon 3년 전 0

예제도 맞고, 사이클 반례도 넣어보았어요.

그런데 저지에 들어가면 퍼센테이지가 오르다 틀리는 것도 아니고,

넣자마자 틀려버리는데....

뭔가 실수한 게 아닐까 싶습니다.

하지만 못 찾고 있어요ㅠㅠ

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int n, m, can_hack[maxn+1], maxSum;
bool visited[maxn+1];
vector<int> adj[maxn+1], ans;

int dfs(int s) {
    if (visited[s]) return can_hack[s];
    visited[s] = true;
    can_hack[s] = 1;
    for (int u : adj[s]) {
        can_hack[s] += dfs(u);
    }
    return can_hack[s];
}

int main() {
    cin >> n >> m;
    //그래프 간선 입력받기
    while (m--) {
        int a, b; cin >> a >> b;
        adj[b].emplace_back(a);
    }
    //값이 원래 최댓값을 넘어서 버리면 다 지우고 갱신
    //같으면 같이 남김
    //그리고 visited 초기화
    for (int i = 1; i <= n; ++i) {
        int tmp = dfs(i);
        if (maxSum < tmp) {
            maxSum = tmp;
            ans.clear();
            ans.emplace_back(i);
        } else if (maxSum == tmp) {
            ans.emplace_back(i);
        }
        memset(visited+1, 0, n);
    }
    for (auto p: ans) cout << p << ' ';
}

slah007 3년 전 0

cycle이 있는 경우 can_hack[]에 의도한 대로의 값이 들어가지 않을 것 같습니다.

6 5
1 2
2 3
3 1
4 5
5 6

dohoon 3년 전 0

엇... 그러네요!

제대로 보지 않은 제 불찰입니다...

감사합니다!!

dohoon 3년 전 0

여전히 넣자마자 틀려버리네요...

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int n, m, can_hack[maxn+1], maxSum;
bool visited[maxn+1];
vector<int> adj[maxn+1], ans;

int dfs(int s) {
    if (visited[s]) return can_hack[s]-1;
    visited[s] = true;
    can_hack[s] = 1;
    for (int u : adj[s]) {
        can_hack[s] += dfs(u);
    }
    return can_hack[s];
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b; cin >> a >> b;
        adj[b].emplace_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        int tmp = dfs(i);
        if (maxSum < tmp) {
            maxSum = tmp;
            ans.clear();
            ans.emplace_back(i);
        } else if (maxSum == tmp) {
            ans.emplace_back(i);
        }
        memset(visited+1, 0, n);
    }
    for (auto p: ans) cout << p << ' ';
}

byeongkeunahn 3년 전 1

DFS를 할 때 이미 방문한 정점은 can_hack[s] - 1이 아니라 아무 것도 더하지 않아야 하지 않을까 싶습니다.

12 11

2 1

3 2

4 2

5 1

2 5

6 7

7 8

8 9

9 10

10 11

11 12

-> should print 12, but prints 1 12

dohoon 3년 전 0

사당합니다..!

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

문제

문제

출처

ICPC

dfs 그래프의 요소들 중 최대 크기 찾는 문제, 반례가 뭘까요..?

dohoon 3년 전 0

slah007 3년 전 0

dohoon 3년 전 0

dohoon 3년 전 0

byeongkeunahn 3년 전 1

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말