---
tags: 圖論
title: 真‧基礎圖論
description: 圖論簡介
---

# 圖論1
[給個玩具](https://domen111.github.io/Draw-Graph/)
1 2 8
2 4 3
1 3 4
4 5 1
4 6 -6
3 5 -2

## 介紹幾個名詞
- 節點(node / vertex)：你看到①②③④⑤⑥的地方，就是節點
- 邊(edge)：你看到的每一條線
- 邊權(weight)：你看到線上的每個數字

## 圖的儲存

//version 1
int edges[1e3][1e3];
edges[A][B] = W;//A -> B
edges[B][A] = W;//B -> A

//version 2
vector<int> edges[1e5];
vector<int> weights[1e5];
edges[A].push_back(B);//edges[A] = {B}
weights[A].push_back(W);//weights[A] = {W}
edges[B].push_back(A);//edges[B] = {A}
weights[B].push_back(W);//weights[B] = {W}

## 圖的走訪
假設從①開始走訪

vector<int> edges[1e5];
vector<int> weights[1e5];

bool vis[1e5];//vis[U] = true 時表示節點U已經走訪過

void dfs(int U){
    vis[U] = true;
    for(int i = 0; i < edges[U].size(); ++i){
        int nxt = edges[U][i];
        if(!vis[nxt]){
            dfs(nxt);
        }
    }
    
    // 看情況做或不做
    vis[U] = false;
}

## 樹
def: 沒有環的無向圖

### 介紹幾個名詞
- 根節點(root)：起點（只有一個點）
- 葉節點(leaf)：終點（不只一個點）
- 父節點(parent)：以根節點遍歷，A->B，且先走訪到A時，A為B的父節點（對於每個節點而言，只有一個）
- 子節點(child)：以根節點遍歷，A->B，且先走訪到A時，B為A的子節點（對於每個節點而言，有0或多個）
- 子樹(subtree)：一個節點的child當root的樹

詳情見樹筆記：https://hackmd.io/D7-rINgnTq62HjKp62sfjQ

# CF 1398C
sum[i] = a[1]+a[2]+...+a[i];
區間和基本算法: 區間 l~r 和為 sum[r] - sum[l-1]

sum[r] - sum[l-1] = 0 => sum[r] == sum[l-1]
區間 l~r 的和為0，當且僅當 sum[r] == sum[l-1]

for i in {1~n}: ans += $\|$ {sum[j] where (j < i)} $\|$

int cnt[1e6+5];//cnt[5] = 3 代表前綴和為5的有3個