글 읽기 - 단절선에 관련된 문제인지 질문드립니다.

20rnjsekdns 1년 전 0

문제에서 어떤 한 pair라도 없어지면 모두에게 연락이 닿지 않게 되는 경우를 구하는 것 같아서 단절선을 구하는 문제인줄 알았는데 여러번 코드를 수정해보아도 답이 나오질 않습니다. 그래서 이게 단절점 문제인지 단절선 문제인지 핀트를 못 잡는 것인지 혹은 저의 코드에 문제가 있는 것인지 확인하고 싶습니다.

#include <iostream>
#include <vector>
#include <memory.h>
#define MAX 100
using namespace std;

vector<int> adj[MAX];
int visitedOrder[MAX];
int order = 0;
int cnt = 0;
int p, c;

int dfs(int now, int par){
    int minOrder = visitedOrder[now] = ++order;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(next == par) continue;
        
        if(visitedOrder[next] == -1){
            int childOrder = dfs(next, now);
            
            if(childOrder > visitedOrder[now]){
                cnt++;
                //cout << "Edges: " << now << ' ' << next << '\n';
            }
            
            minOrder = min(minOrder, childOrder);
        }
        else{
            minOrder = min(minOrder, visitedOrder[next]);
        }
    }
    
    //cout << "node: " << now << " visitedOrder: " << visitedOrder[now] << " minOrder: " << minOrder << '\n';
    return minOrder;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    while(true){
        cin >> p >> c;
        if(p == 0 && c == 0) break;
        
        // init
        for(int i = 0; i < MAX; i++) adj[i].clear();
        memset(visitedOrder, -1, sizeof(visitedOrder));
        order = 0;
        cnt = 0;
        
        for(int i = 0; i < c; i++){
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        dfs(0, -1);
        
        if(cnt) cout << "Yes";
        else cout << "No";
        cout << '\n';
    }
    
    return 0;
}

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

문제

문제

출처

ICPC

단절선에 관련된 문제인지 질문드립니다.

20rnjsekdns 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말