POJ 2492 이분 도 판단 및 수집

4395 단어 -----------알고리즘----------도 론--------이분 도
POJ - 2492 제목: N 개의 BUG 와 M 개의 BUG 의 성관 계 를 제시 하여 동성 관계 여 부 를 판단 한다.
이분 도 판단 해서 할 수도 있 고, 병 찰 집 으로 할 수도 있 고, 내일 보충 해서 집 을 찾 을 수도 있어 요.
이분 도:
만약 에 이 N 개의 BUG 간 에 이성 간 에 만 관계 가 있다 면 이 N 개의 BUG 에 대해 하나의 관계 도 를 만 들 고 동성 간 의 BUG 간 에 관계 가 없 으 며 서로 다른 성별 간 에 점 집 을 두 가지 유형 으로 나 눌 수 있다. A B 집합 내부 에 관계 가 없 으 면 이 그림 은 2 분 의 그림 으로 판단 하 는 데 자주 사용 되 는 방법 이다.그림 염색법 두 가지 색 은 그림 을 인접 점 을 서로 다른 색 으로 염색 할 수 있 으 며 이분 도 는 DFS 로 이분 도 에 구멍 이 있 는 지 판단 한다. 이 그림 은 몇 개의 이분 도 로 구 성 된 그림 일 수 있 으 므 로 모든 연결 도 를 판단 해 야 한다.
코드 는 다음 과 같 습 니 다:
#include 
#include 
#include 
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 2000 + 5;
int color[maxn];
bool Adj[maxn][maxn];
int n,m;
bool DFS(int cur){
    for(int i = 1;i <= n;++i){
        if(Adj[i][cur]){
            if(color[i] == color[cur]){
                return false;
            }
            if(color[i] == -1){
                color[i] = color[cur] == 0 ? 1 : 0;
                if( DFS(i) == false ) return false;
            }
        }
    }
    return true;
}
int main(){
    int T;sf("%d",&T);
    int ca = 0;
    while(T--){
        sf("%d%d",&n,&m);
        memset(Adj,0,sizeof(Adj));
        for(int i = 0;i < m;++i){
            int u,v;sf("%d%d",&u,&v);
            Adj[u][v] = Adj[v][u] = 1;
        }
        memset(color,-1,sizeof(color));
        bool ans = true;
        for(int i = 1;i <= n;++i){
            if(color[i] == -1){
                color[i] = 0;
                ans = DFS(i);
            }
            if(!ans) break;
        }
        pf("Scenario #%d:
",++ca);
        if(ans){
            pf("No suspicious bugs found!
");
        }
        else pf("Suspicious bugs found!
");
        if(T) pf("
");
    }
    return 0;
}
알 리 바 바 알고리즘 강 프로 그래 밍 문제: 초보 창고
[백준] 1157번 : 단어 공부 (파이썬)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage