# 期末程式
# Min Heap 插入節點

#include <stdio.h>
#include <stdlib.h>

#define MXN 200005

void insert_heapify(int* v, int x) {
    if (x <= 0) return;  // 如果是root 結束遞迴

    int f = (x - 1) / 2;  // 父節點索引
    if (v[x] < v[f]) {
        // 當前節點小於父節點 交換並繼續檢查
        int temp = v[x];
        v[x] = v[f];
        v[f] = temp;
        insert_heapify(v, f);
    }
}

void solve() {
    int* v = (int*)malloc(MXN * sizeof(int)); 
    if (!v) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }

    int cnt = -1;  
    int u;

    while (scanf("%d", &u) != EOF) {  
        v[++cnt] = u;  
        insert_heapify(v, cnt);  
      
        for (int i = 0; i <= cnt; i++) {
            printf("[%d]%d ", i + 1, v[i]);
        }
        printf("\n");
    }

    free(v);  
}

int main() {
    solve();
    return 0;
}

# 二元搜尋樹刪除節點

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


typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;


TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}


TreeNode* insert(TreeNode* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}


void preorder(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}


TreeNode* findMax(TreeNode* root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}

TreeNode* deleteNode(TreeNode* root, int key, int* found) {
    if (root == NULL) {
        return NULL;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key, found);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key, found);
    } else {
        
        *found = 1;

        // 無子節點
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
       
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 有兩個子節點：用左子樹中最大值取代
        TreeNode* maxNode = findMax(root->left);
        root->data = maxNode->data;
        root->left = deleteNode(root->left, maxNode->data, found);
    }
    return root;
}


int main() {
    TreeNode* root = NULL;
    int value;
    char line[1000];

    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, " ");
    while (token != NULL) {
        value = atoi(token);
        root = insert(root, value);
        token = strtok(NULL, " ");
    }

    printf("Binary search tree (before):\n");
    preorder(root);
    printf("\n");

  
    fgets(line, sizeof(line), stdin);
    token = strtok(line, " ");
    while (token != NULL) {
        value = atoi(token);
        int found = 0;
        root = deleteNode(root, value, &found);
        if (!found) {
            printf("no %d\n", value);
        }
        token = strtok(NULL, " ");
    }

    printf("Binary search tree (after):\n");
    preorder(root);
    printf("\n");

    return 0;
}

# MIN HEAP 刪除節點

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MXN 200005

// 插入操作的堆调整
void insert_heapify(int v[], int x) {
    if (x == 0) return;
    int f = (x - 1) >> 1; // 父节点索引
    if (v[x] < v[f]) {
        int temp = v[x];
        v[x] = v[f];
        v[f] = temp;
        insert_heapify(v, f);
    }
}


void delete_heapify(int v[], int n, int x) {
    int smallest = x;
    int l = (x << 1) + 1; // 左子节点索引
    int r = (x << 1) + 2; // 右子节点索引
    if (l < n && v[l] < v[smallest]) smallest = l;
    if (r < n && v[r] < v[smallest]) smallest = r;
    if (smallest != x) {
        int temp = v[x];
        v[x] = v[smallest];
        v[smallest] = temp;
        delete_heapify(v, n, smallest);
    }
}

void solve() {
    
    int* v = (int*)malloc(MXN * sizeof(int));
    if (!v) {
        fprintf(stderr, "Memory allocation failed for heap array\n");
        return;
    }

    
    char* input = (char*)malloc(MXN * 10 * sizeof(char));
    if (!input) {
        fprintf(stderr, "Memory allocation failed for input buffer\n");
        free(v);
        return;
    }

    int cnt = -1;

 
    if (fgets(input, MXN * 10, stdin) == NULL) {
        free(v);
        free(input);
        return;
    }

   
    int num = 0, in_number = 0;
    for (char* p = input; *p != '\0'; p++) {
        if (isdigit(*p)) {  
            num = num * 10 + (*p - '0');
            in_number = 1; 
        }
        else if (in_number) {  
            v[++cnt] = num;
            insert_heapify(v, cnt);
            num = 0;
            in_number = 0;
        }
    }
  
    if (in_number) {
        v[++cnt] = num;
        insert_heapify(v, cnt);
    }

  
    for (int i = 0; i <= cnt; i++) {
        printf("[%d]%d ", i + 1, v[i]);
    }
    printf("\n");

    
    while (cnt >= 0) {
        v[0] = v[cnt];
        cnt--;
        delete_heapify(v, cnt + 1, 0);

        for (int i = 0; i <= cnt; i++) {
            printf("[%d]%d ", i + 1, v[i]);
        }
        printf("\n");
    }

    free(v);
    free(input);
}

int main() {
    solve();
    return 0;
}


# Almost Union-Find

#include <stdio.h>

#define MAX 200001

long long sum[MAX];
int par[MAX], r[MAX], coor[MAX];

// 查找并查集的根
int searchroot_(int x) {
    if (par[x] != x) {
        par[x] = searchroot_(par[x]);
    }
    return par[x];
}

// 合并两个集合
void unite(int x, int y) {
    x = searchroot_(x);
    y = searchroot_(y);
    if (x == y) {
        return;
    }
    if (r[x] < r[y]) {
        par[x] = y;
        sum[y] += sum[x];
        r[y] += r[x];
    } else {
        par[y] = x;
        sum[x] += sum[y];
        r[x] += r[y];
    }
}

int main() {
    int n, com;
    while (scanf("%d %d", &n, &com) != EOF) {
        for (int i = 1; i <= n + com; i++) {
            par[i] = i;
            r[i] = 1;
            sum[i] = i;
            coor[i] = i;
        }

        int c, in1, in2;
        while (com--) {
            scanf("%d %d", &c, &in1);
            if (c == 1) {
                scanf("%d", &in2);
                unite(coor[in1], coor[in2]);
            } else if (c == 2) {
                scanf("%d", &in2);
                int par1 = searchroot_(coor[in1]);
                int par2 = searchroot_(coor[in2]);
                if (par1 != par2) {
                    sum[par1] -= in1;
                    r[par1]--;
                    n++;
                    coor[in1] = n;
                    par[n] = n;
                    sum[n] = in1;
                    r[n] = 1;
                    unite(coor[in1], coor[in2]);
                }
            } else if (c == 3) {
                int p = searchroot_(coor[in1]);
                printf("%d %lld\n", r[p], sum[p]);
            }
        }
    }
    return 0;
}


# 相鄰矩陣與相鄰串列

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define MXN 10005

// 稀疏鄰接矩陣
map<int, map<int, int>> board;
// 鄰接表
vector<int> edge[MXN];

void solve() {
    int u, v, mx = -1;

  
    while (cin >> u >> v) {
        // 忽略自環
        if (u == v) continue;

        
        board[u][v] = 1;
        board[v][u] = 1;

       
        if (find(edge[u].begin(), edge[u].end(), v) == edge[u].end()) {
            edge[u].push_back(v);
        }
        if (find(edge[v].begin(), edge[v].end(), u) == edge[v].end()) {
            edge[v].push_back(u);
        }

       
        mx = max({mx, u, v});
    }

   
    cout << "Adjacency matrix:\n";
    for (int i = 0; i <= mx; i++) {
        for (int j = 0; j <= mx; j++) {
            cout << (board[i][j] ? 1 : 0) << " \n"[j == mx];
        }
    }

   
    cout << "\nAdjacency list:\n";
    for (int i = 0; i <= mx; i++) {
        cout << i << ": ";
        sort(edge[i].begin(), edge[i].end()); 
        for (int j : edge[i]) {
            cout << j << " -> ";
        }
        cout << "end\n";
    }
}

int main() {
    solve();
    return 0;
}


# 網路連通性

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> edge;
vector<bool> vis;

void dfs(int x) {
    vis[x] = true;
    for (int i : edge[x]) {
        if (!vis[i]) {
            dfs(i);
        }
    }
}

void solve() {
    int n, x;
    cin >> n;
    if (n <= 0) {
        cout << "-1\n";
        return;
    }
    edge.assign(n, vector<int>());
    vis.assign(n, false);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> x;
            if (x && i != j) {
                edge[i].push_back(j);
            }
        }
    }
    dfs(0);
    if (count(vis.begin(), vis.end(), true) == n) {
        cout << "1\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    solve();
    return 0;
}


# DFS 與 BFS

#include <iostream>
#include<vector>
#include<queue>
#include <algorithm>
using namespace std;
#define MXN 100005

vector<int> edge[MXN];//element adjacency list of a vertex
vector<bool>vis;
vector<int> res1, res2;// store traversal order of vertices for DFS and BFS respectively.

void dfs(int x)
{/* 從一個點x開始對這個圖的深度優先搜尋 */
    vis[x] = true;
    res1.push_back(x);
    for (int i : edge[x]) {
        if (vis[i]) {
            continue;
        }
        dfs(i);
    }

}

void solve() {
    int u, v, mx = -1;
    while (cin >> u >> v) {
        edge[u].push_back(v);
        edge[v].push_back(u);
        mx = max({ mx, u, v });
    }
    vis.clear();
    vis.resize(mx + 1, false);
    dfs(0);
    cout << "Depth First Search:\n";
    for (int i = 0; i < res1.size(); i++) {
        cout << res1[i] << " \n"[i == res1.size() - 1];
    }
    vis.clear();
    vis.resize(mx + 1, false);
    queue<int> que;
    que.push(0);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        if (!vis[x]) {
            res2.push_back(x);
        }
        vis[x] = true;
        for (int i : edge[x]) {
            if (!vis[i]) {
                que.push(i);
            }
        }
    }
    cout << "\nBreadth First Search:\n";
    for (int i = 0; i < res2.size(); i++) {
        cout << res2[i] << " \n"[i == res2.size() - 1];
    }
   
}

int main() {
    solve();
    return 0;

}

/*
Depth First Search:
0 3 1 2

Breadth First Search:
0 3 1 2

*/


# 計算圖形的 low 與 dfn 值

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

#define MXN 100005
#define MAX_EDGES 200005

typedef struct {
    int n, step;
    int dfn[MXN], low[MXN];
    int *edge[MXN];
    int edgeCount[MXN];
} Solution;

Solution graph;

void init(Solution *graph, int _n) {
    graph->n = _n;
    graph->step = 0;
    for (int i = 0; i < _n; i++) {
        graph->edge[i] = malloc(sizeof(int) * MAX_EDGES);
        graph->edgeCount[i] = 0;
        graph->dfn[i] = -1;
        graph->low[i] = -1;
    }
}

void addEdge(Solution *graph, int u, int v) {
    graph->edge[u][graph->edgeCount[u]++] = v;
    graph->edge[v][graph->edgeCount[v]++] = u;
}

void dfs(Solution *graph, int x, int f) {
    graph->dfn[x] = graph->low[x] = graph->step++;
    for (int i = 0; i < graph->edgeCount[x]; i++) {
        int next = graph->edge[x][i];
        if (next == f) continue;
        if (graph->dfn[next] == -1) {
            dfs(graph, next, x);
            graph->low[x] = (graph->low[x] < graph->low[next]) ? graph->low[x] : graph->low[next];
        } else {
            graph->low[x] = (graph->low[x] < graph->dfn[next]) ? graph->low[x] : graph->dfn[next];
        }
    }
}

void printSol(Solution *graph) {
    printf("    ");
    for (int i = 0; i < graph->n; i++) {
        printf("%d%s", i, (i == graph->n - 1) ? "\n" : " ");
    }
    printf("dfn ");
    for (int i = 0; i < graph->n; i++) {
        printf("%d%s", graph->dfn[i], (i == graph->n - 1) ? "\n" : " ");
    }
    printf("low ");
    for (int i = 0; i < graph->n; i++) {
        printf("%d%s", graph->low[i], (i == graph->n - 1) ? "\n" : " ");
    }
}

void solveGraph(Solution *graph) {
    for (int i = 3; i < graph->n; i++) {
        if (graph->dfn[i] == -1) {
            dfs(graph, i, i);
        }
    }
    for (int i = 0; i < 3; i++) {
        if (graph->dfn[i] == -1) {
            dfs(graph, i, i);
        }
    }
    printSol(graph);
}

void solve() {
    int u, v, mx = -1;
    int edge[MAX_EDGES][2];
    int edgeCount = 0;

    while (scanf("%d %d", &u, &v) != EOF) {
        edge[edgeCount][0] = u;
        edge[edgeCount][1] = v;
        edgeCount++;
        mx = (mx > u) ? mx : u;
        mx = (mx > v) ? mx : v;
    }

    init(&graph, mx + 1);
    for (int i = 0; i < edgeCount; i++) {
        addEdge(&graph, edge[i][0], edge[i][1]);
    }
    solveGraph(&graph);

    // Free allocated memory
    for (int i = 0; i < graph.n; i++) {
        free(graph.edge[i]);
    }
}

int main() {
    solve();
    return 0;
}


# 很油的田

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

#define MAX 100  // 假设最大网格尺寸为 100x100

int dx[] = { -1, 1, 0, 0, -1, 1, -1, 1 };
int dy[] = { 0, 0, -1, 1, -1, -1, 1, 1 };

void dfs(char grid[MAX][MAX], bool visited[MAX][MAX], int x, int y, int n, int m) {
    visited[x][y] = true;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] == '@' && !visited[nx][ny]) {
            dfs(grid, visited, nx, ny, n, m);
        }
    }
}

int main() {
    int n, m;

    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        char grid[MAX][MAX];
        bool visited[MAX][MAX] = {false};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf(" %c", &grid[i][j]);
            }
        }

        int pos = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@' && !visited[i][j]) {
                    dfs(grid, visited, i, j, n, m);
                    pos++;
                }
            }
        }

        printf("%d\n", pos);
    }
    return 0;
}