[BOJ 30870 사이클 없는 그래프 c++ 풀이]

문제 링크

코드

 

문제

주어진 그래프에서 t 단계 별로 인접한 노드와 연결 엣지 지워나감.

최초로 사이클 생성되지 않는 t 구하기

N,M <= 200,000

 

풀이 전략

사이클이 사라지는 것을 찾긴 어렵다.  → 사이클 생성 여부 확인으로 바꾸면 쉽다.

주어진 순서대로 간선을 지우고 사이클 생성 여부를 확인 , 지울때마다 사이클을 판단 → TLE

그렇다면 역순으로 판단하자. 

 

마지막에 사라졌던 간선들부터 시작하여 처음 사라진 간선들 순서로 그래프가 복원하자.

간선이 지워지는 역순으로 그래프를 생성해나가 보면, 어느 순간 사이클 발생 

→  (전체 T - 사이클 생성 되는 t) 가 답

 

요약

• 간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용
• 지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단
  • 인풋으로 주어지는 K개 시작 노드를 기준으로 t 단계에 지워지는 간선 저장.
  •  => BFS, Stack 이용
• 사이클 판단은 union-find로 판단 : merge가 안되는 경우 = 이미 같은 부모 = 사이클
  • 사이클 생성 여부 disjoint set
  • Union Find

 

3가지 오류

문제 풀며 틀렸던 부분을 정리해봤다.

1. 사이클 제거를 순차적으로 접근
   1. 초기 K개 주어진 노드를 시작으로 해당 노드와 연결된 relation을 지운 상태에서 사이클 형성 여부 검사하고
   2. 다시 연결된 노드를 지우고 검사하고
   3. 이 방법 자체로 시간 초과다. 순차접근이 아닌 역으로 접근하는게 이 문제의 핵심이다.   
2. 사이클 제거 시 relation 전체를 반복적으로 접근했다.
   1. 예로, 1번 노드 제거하고 1번 노드와 관련된 노드만 보는 것이 아닌 전체 relation을 보며 1번 관련된거면 pass하고 이런 식으로 전체 관계를 반복적으로 매 스텝마다 봤다.
   2. relation 200,000개 → 이걸로 제거한 사이클 찾거나 새로 만들고 반복적으로 하면 TLE, 메모리 초과
3. 중복 간선 주어진 경우
   1. 인풋에 주어지는 중복 간선을 제거하고 시작하라는 의미라고 해석했지만, 중복 간선 또한 사이클 발생하는 요소로 생각해야한다.

 

 

틀린 코드 →  2번 오류 케이스

#include<iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
//#include <tuple>

#define MAX_N 200001
using namespace std;
typedef pair<int, int> pii;

int N, M;
vector<pii> relation;
vector<int> toDel; // 지울 노드
stack<vector<pii>> toAdd; // 역순 

bool erased[MAX_N + 1] = { 0, };
int par[MAX_N + 1];

int Find(int a) {
    if (a == par[a]) return a;
    return par[a] = Find(par[a]);
}

bool Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return false;
    par[b] = a;
    return true;
}

bool hasCycle(vector<pii>& vec) {
    for (const pii& p : vec) {
        if (!Union(p.first, p.second))
            return true; // 사이클 형성 관계
    }
    return false;// 사이클 안생긴다.
}


void bfs() {
    // 지워야할 엣지 사전에 구하기 
    while (M) {
        vector<pii> add_rel; // stack에 추가될 
        vector<pii> new_rel; // 아직 추가되지 않은 
        
        for (int e : toDel) erased[e] = true;
        toDel.clear();

        for (const pii& p : relation) {
            int u = p.first, v = p.second;

            // 둘다 사용 안됨
            if (!erased[u] && !erased[v]) {
                new_rel.push_back({ u,v }); 
                continue;
            }

            // 둘 중 하나라도 사용됨. 지울 대상 
            add_rel.push_back({ u,v });
            if (!erased[u])toDel.emplace_back(u);
            if (!erased[v])toDel.emplace_back(v);
        }

        M -= add_rel.size();
        toAdd.push(move(add_rel));
        relation = move(new_rel);
    }
}

int solve() {
    bfs(); //관계 역순 형성 

    int ret = toAdd.size();
    for (int i = 1; i <= N; i++) par[i] = i;
    while (!toAdd.empty()) {
        ret--;
        if (hasCycle(toAdd.top())) 
            break;
        toAdd.pop();
    }
    return ret + 1;
}

void input() {
    int K;
    cin >> N >> M >> K;

    // 중복 없는 간선 위해
    set<pii> s;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        if (b < a) swap(a, b);
        s.insert({ a,b });
    }

    relation.assign(s.begin(), s.end());

    while(K--) {
        int a; 
        cin >> a;
        toDel.emplace_back(a);
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    cout << solve();
    return 0;
}

 

 

최종 코드

#include<iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

#define MAX_N 200001
using namespace std;
typedef pair<int, int> pii;

int N, M;
vector<int> relation[MAX_N+1];
stack<vector<pii>> toAdd; // 역순 
queue<int> toDel;

bool erased[MAX_N + 1] = { 0, };
int par[MAX_N + 1];

int Find(int a) {
    if (a == par[a]) return a;
    return par[a] = Find(par[a]);
}

bool Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return false;
    par[b] = a;
    return true;
}

bool hasCycle(vector<pii>& vec) {
    for (const pii& p : vec) {
        if (!Union(p.first, p.second))
            return true; // 사이클 형성 관계
    }
    return false;// 사이클 안생긴다.
}

void bfs(int n) {
    while (n) {
        int cnt = toDel.size();
        toAdd.push(vector<pii>() );
        vector<pii> &vec = toAdd.top();
        while (cnt--) {
            int curr = toDel.front();
            toDel.pop();
            if (erased[curr]) continue;
            erased[curr] = true;
            n--;

            for (int nex : relation[curr]) {
                if (erased[nex]) continue;
                vec.push_back({ curr,nex });
                toDel.push(nex);
            }
        }
    } 
}

int solve() {
    bfs(N); //관계 역순 형성 

    while (toAdd.top().empty())toAdd.pop();
    int ret = toAdd.size();
    for (int i = 1; i <= N; i++) 
        par[i] = i;
    while (!toAdd.empty()) {
        ret--;
        if (hasCycle(toAdd.top())) 
            break;
        toAdd.pop();
    }
    return ret + 1;
}

void input() {
    int K;
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        relation[a].push_back(b);
        relation[b].push_back(a);
    }

    while(K--) {
        int a; 
        cin >> a;
        toDel.push(a);
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    cout << solve();
    return 0;
}