主題

[OJ練習] 10004 (DFS的應用) 到底是我笨還是這新東西真的不好懂

テリ君(桃夫模式) | 2022-12-07 12:26:06 | 巴幣 120 | 人氣 231

10004 (4/5)

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool path[201][201];

bool DFS(int pointColor[], int i, int n, int color){
    int change_color = color ^ 3; // 1 ^ 3 = 2 ; 2 ^ 3 = 1 (In binary and it's a loop)
    bool answer = true;

    if(pointColor[i]){
        if(pointColor[i] != color) return false;
        if(pointColor[i] == color) return true;
    }

    pointColor[i] = color;

    for(int j = i + 1; j < n; j++){
        if(path[i][j]) answer &= DFS(pointColor, j, n, change_color);
        // &= means AND logic gate for left and right so if 1 &= 0 -> 0 0 and so on.
    }

    return answer;
}

/*
void printPath(int n){
    printf("\n");
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            printf("%d ", path[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
*/

int main(){
    int n, l, n1, n2;
    int pointColor[201];

    while(scanf("%d", &n) != EOF && n != 0){
        // The input consists of several test cases.
        // Each test case starts with a line containing the number n
        // An input with n = 0 will mark the end of the input and is not to be processed.
        scanf("%d", &l);
        // after this, l lines will follow
        memset(pointColor, 0, sizeof(pointColor)); // init the point
        memset(path, false, sizeof(path)); // init the path
        // each containing two numbers that specify an edge
        // between the two nodes that they represent.
        for(int i = 0; i < l; i++){
            scanf("%d%d", &n1, &n2);
            path[n1][n2] = true;
            // the graph is nondirected. That is,
            // if a node a is said to be connected to a node b,
            // then you must assume that b is connected to a.
            path[n2][n1] = true;
        }

        //printEdge(n); // check edges

        if(DFS(pointColor, 0, n, 1)) printf("BICOLORALBE.\n");
        else printf("NOT BICOLORABLE.\n");
    }

    return 0;
}

我找到的是C++的寫法，我把它轉成C，但我真的除了會轉之外，我讀了好幾遍才大概知道他在幹嘛= =

第一個主要是要先知道題目是說，先輸入有幾個節點(n)，之後再輸入要連結各節點的數量(l)，接下來像是

3
3
0 1
1 2
2 0

這種輸入

就是三個節點、三個連結

出來的圖形會長這樣

那因為題目的主要訴求是要判定是否Bicolorable，所以要確定相連的各點之間是否能用兩種顏色做區隔

所以像是上述這個就是Not Bicolorable，因為 0 接 1 可以用兩種顏色，1 接 2 ，2 也可以用 0 的顏色，但當 2 接 0 的時候就發現顏色一樣了，不能區隔開來，因此就歸類於 Not Bicolorable.

那就是要先讓陣列path可以先儲存哪兩個點兩兩相連，之後用DFS(depth first search)深度優先搜尋法去上色之後尋找說哪個節點是Not Bicolorable，因為優先做深度搜尋可以最快找到哪個後面的點有跟前面的點有相連以及是否撞色，若撞色則DFS function return False，若搜尋到底都沒事就是 return True。

基本上就是用for迴圈去檢測，且先檢定是否該點有上色，若無就直接跳過，若有才做是否有換色及AND匣的判定，若有兩點相連且顏色相同則輸出為 False，反之則True。

大致上是這樣，希望我的理解是正確的，因為最近也想要來用Python著手寫一些BFS和DFS的演算法，但願學期結束前有些成果吧...

這題對於理解力很強且有前置知識的人來說應該是易如反掌，但對我，一個沒接觸過這種演算方式的人來說，是真的需要時間的，拖了三天今天終於可以好好的釐清這段Code到底在幹嘛，我還看了好幾個影片去做註解和確認是否運作= =，由衷盼望這次經驗可以對未來有幫助...