글 읽기 - 이분 탐색으로는 주어진 시간 내에 풀수 없는 문제인가요?

manybirds 3년 전 2

binary search로 cycle 여부를 탐지하려고 했는데

dfs는 stack overflow가 나는 것 같고 bfs는 그냥 시간 초과가 나네요.

n(E)가 2백만 정도라 O((V+E)logE) 정도면 비벼볼 만 하다고 생각했는데

혹시 제가 잘못 생각하고 있는 것인지 궁금합니다.

아래는 제 dfs 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool dfs(const vector<vector<pair<int, int>>> &g, vector<bool> &visit, int m, int s, int u) {
    visit[u] = true;
    for (pair<int, int> p : g[u]) {
        int v = p.first;
        int t = p.second;
        if (t > m || v == s) {
            continue;
        }
        if (visit[v] || (!visit[v] && dfs(g, visit, m, u, v))) {
            return true;
        }
    }
    return false;
}

int search(const vector<vector<pair<int, int>>> &g, int l, int r) {
    if (l == r) {
        return l;
    }
    int m = (l + r) / 2;
    vector<bool> visit(g.size());
    bool cycle = false;
    for (int i=0; i<g.size(); i++) {
        if (!visit[i]) {
            cycle = cycle || dfs(g, visit, m, i, i);
        }
    }
    if (cycle) {
        return search(g, l, m);
    } else {
        return search(g, m + 1, r);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i + 1});
        g[v].push_back({u, i + 1});
    }
    int i = search(g, 1, m + 1);
    if (i == m + 1) {
        cout << 0;
    } else {
        cout << i;
    }
    return 0;
}

112224 3년 전 0

음 방식은 이해가 되지만 유니온파인드라는 자료 구조로 푸시는 것이 정해입니다!

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

문제

문제

출처

ICPC

이분 탐색으로는 주어진 시간 내에 풀수 없는 문제인가요?

manybirds 3년 전 2

112224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말