사이클 검출(Cycle Detection)

DFS를 이용한 방법

DFS를 사용한 사이클 검증법은 보통 $O(V)$로 이야기 되는 것 같다. 만약 간선이 많다고 하더라도 V번 안에 back edge가 발견돼서 끝나서 그런듯. (끝까지 사이클이 없는 경우에 최대 V정점, 최대 V간선을 방문하니 2V라서 $O(V)$가 맞긴한듯)

 

back edge를 발견하면 사이클이 있다고 판단하는건데, 순회와 백엣지 개념은 여기가 설명 잘되어 있다.

 

코드는 여기가 좋은 것 같긴한데.. 문제는 딱맞는 샘플문제가 없어서 해보지 못했다

 

여기에 샘플문제가 있고 제출도 가능한것 같아서 해보는 중.

 

DFS로 직접 한 번 구현해보니까, visit배열만 있어도 판단이 되는데, visit를 1로했다 0으로 했다하는 테크닉이 필요했다.아래 cache는 나중에 추가했는데.. 저거 없어도 위에 샘플이 돌긴하는데 TLE가 나길래 추가했고, 추가한 후에 AC떴다.

#include <bits/stdc++.h>
using namespace std;
 
 
int V, E, u, v, w, in[101][101], visited[101], cache[101];
 
int DFS_has_cycle(int cur_v) {
    if (cache[cur_v] != INT_MAX) return cache[cur_v];
    visited[cur_v] = 1;
    for (int i = 0; i < V; i++) {
        if (in[cur_v][i]){
            if (visited[i]) return cache[cur_v] = 1;  //back-edge발견, 사이클!
            if (DFS_has_cycle(i)) return cache[cur_v] = 1;
        }
    }
    visited[cur_v] = 0;  // 이부분이 중요(back track한다음에는 0으로 만들어줘야 트리구조로 들어간다.)
    return cache[cur_v] = 0;
}
 
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d", &V, &E);
    fill(&in[0][0], &in[V][V], 0);
    for (int i = 0; i < E; i++) {
        scanf("%d%d", &u, &v);
        in[u][v] = 1;
    }
    
    bool ans = false;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < 101; j++)visited[j]=0, cache[j]=INT_MAX;
        if (DFS_has_cycle(i)) { ans = true; break; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}
 

근데, 내가 다른사람하고 같은 방식으로 짰는지는 잘 모르겠다;; 

뭔가 여러가지 방식이 있는 느낌이라 좀 헷갈린다.

 

나중에 다른 문제를 풀다가 위의 구현을 썼더니 TLE가 나서 아래 구현으로 바꿨더니 통과했다; 아직 위의 구현에 어떤 문제땜에 느린지 파악은 못함

음 파악해 봤는데.. 위에서 매번 visited, cache 초기화 해주는게 O(N)이다 보니 모든 노드에 대해서 DFS_has_cycle()부르면 O(N^2)이상이 될 수 있는게 문제였다 ㄷ. 아래 소스는 cache는 아예 안쓰고, visited도 한번만 초기화해주면 되다보니 빨랐던것

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
 
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(int)> dfs = [&](int cur_v) -> bool {
        if (visited[cur_v]) {
            if (visited[cur_v] == -1) return true;
            return false;
        }
        visited[cur_v] = -1;
        for (int adj : adj_list[cur_v]) {
            if (dfs(adj)) {
                return true;
            }
        }
        visited[cur_v] = 1;
        return false;
    };
    return dfs(cur_v);
}
 
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<int>> adj_list(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        adj_list[u].push_back(v);
    }
 
    bool ans = false;
    for (int i = 0; i < N; i++) {
        if (has_cycle(N, i, adj_list)) { ans = true; break; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}

 

 

그리고 이게또 direct냐 undirect에 따라서도 다른거 같다.(위는 direct 버전)

 

undirect 버전

undirect는 양방향으로 간선을 처리해준다음에, 트리 순회처럼 parent-child관계로 탐색해 나가고, 

바로전(justbefore)으로 돌아가는 간선은 무시해주는 식으로 처리하면 된다.

이 문제를 통해서 볼 수 있고, 완전한 코드는 아니지만, 아래 코드 참조하자.

using vi = vector<int>;
using vvi = vector<vi>;
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(int, int)> DFS = [&](int curr, int justbefore) -> bool {
        visited[curr] = true;
 
        for (auto child : adj_list[curr]) {
            if (child == justbefore) continue;
            // cycle 이 생기면
            if (visited[child]) return false;
            if (DFS(child, curr) == false) return false;
        }
        return true;
    };
    return DFS(cur_v, -1);
}

 

 

그리고 사이클 존재 여부만 판단하느냐, 최소사이클수 같은걸 판단하느냐도 다른듯

최소사이클의 경우는 DFS만으로 커팅하면서 빠르게 판단하기 힘든게 아닌가 생각중

(최소 사이클 나오면 Floyd-Warshall Algorithm이 현재 내가아는한에서는 답이다)

 

 

유니온파인드를 통한 디텍션

undirected의 경우 이 문제의 경우처럼 유니온파인드로도 사이클 디텍션을 할 수 있다.

좀 더 구체적으로는 새로운 간선을 union할 때, 양쪽 정점이 이미 같은 parent를 가지고 있으면, 사이클로 판정가능하다. (중복 간선은 없다는 가정하에, 이미 연결되어 있는데 부가적인 연결이 생기는거라)

간선이 추가되면서 특정 간선이 추가될때 사이클이 완성됨을 판정할때는 dfs보다 유리한 것 같다.

다음은 내 구현이다. 위 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct union_find {
    vector<int> p, r;
    union_find(int n) {
        p.resize(n + 1), r.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
        }
    }
    int find(int x) {
        if (p[x] == x) return x;
        else return p[x] = find(p[x]);
    }
 
    void uni(int a, int b) {
        a = find(a);
        b = find(b);
        if (r[a] < r[b]) p[b] = a;
        else p[a] = b;
        if (r[a] == r[b]) r[a]++;
    }
};
int32_t main()
{
    int n, m; scanf("%d%d", &n, &m);
    union_find uf(n);
    REP(i, m) {
        int u, v; scanf("%d%d", &u, &v);
        if (uf.find(u) == uf.find(v)) {
            printf("%d\n", i + 1);
            return 0;
        }
        else {
            uf.uni(u, v);
        }
    }
    printf("0\n");
    return 0;
}
 

 

 

트리 디텍션과도 일맥상통.