# 圖論和其他資料結構

[toc]

## 圖論
### 圖
| point | child |
| ----- | ----- |
| 1 | 2, 3 |
| 2 | 3 |
| 3 | 4 |
| 4 | |

#### 程式範例

#include <bits/stdc++.h>
using namespace std;
#define lint long long int
#define endl '\n'

int main()
{
    vector<vector<int>> graph(int(1e5), vector<int>());

    // 4
    // 2 2 3
    // 1 3
    // 1 4
    // 0

    int n;
    cin >> n;

    int t, t1;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        for (int j = 0; j < t; j++)
        {
            cin >> t1;
            graph[i].emplace_back(t1);
        }
    }
}

### BFS

在看到一個node時，
把他周圍且沒看過的node放到stack裡，
然後繼續看下一個
#### 程式範例

#define lint long long int
#define endl '\n'

vector<vector<int>> graph(int(1e5), vector<int>());
vector<bool> visited(int(1e5), false);

void bfs(int index)
{
    queue<int> que;
    que.emplace(index);
    visited[index] = true;

    while (!que.empty())
    {
        int current = que.front(); que.pop();
        for(auto c : graph[current])
        {
            if(!visited[c])
            {
                que.emplace(c);
                visited[current] = true;
            }
        }
    }
}

### DFS
當看到一個node時，
一直往第一個沒看過的child node看，
到底了就到上一層的node 繼續向下一個child node看
#### 程式範例

#include <bits/stdc++.h>
using namespace std;
#define lint long long int
#define endl '\n'

vector<vector<int>> graph(int(1e5), vector<int>());
vector<bool> visited(int(1e5), false);

void dfs(int index)
{
    visited[index] = true;
    for(auto c : graph[index])
    {
        if(!visited[c])
            dfs(c);
    }
}

## 拓撲排序

## 資料結構
### Tree

一個無向無環圖

> tree的輸入有好幾種,
> 可以用基本圖的二維陣列方式來記錄,
> 記錄index和他的child index

### Disjoint Set


#### 程式範例

#include <bits/stdc++.h>
using namespace std;
#define lint long long int
#define endl '\n'

vector<vector<int>> graph(int(1e5), vector<int>());
vector<bool> visited(int(1e5), false);

struct disjointSet
{
    vector<int> vec;
    vector<int> size;
    int componentCount;
    int maxSize = 1;

    disjointSet() : vec(int(1e5)), size(int(1e5), 1) {}

    void init(int n)
    {
        for (int i = 1; i <= n; i++)
        {
            vec[i] = i;
        }

        componentCount = n;
    }

    bool find(int x)
    {
        if(vec[x] != x) // not find
            vec[x] = find(vec[x]);
        else // find root
            return x;
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    void Union(int x, int y)
    {
        if(same(x, y)) return;

        x = find(x);
        y = find(y);
        if(size[y] > size[x]) swap(x, y);

        // now x > y, for all x
        vec[y] = x;
        size[x] += size[y];
        componentCount--;
        maxSize = max(size[x], maxSize);
    }


};

int main()
{
    int n; cin >> n;
    disjointSet djs;
    
    // initial
    djs.init(n);

    // use
    djs.Union(1, 2);
    djs.find(1);
}

### BIT

單點加值 : add(int pos, int )
求0~pos的總和 : sum(int pos)

#### 程式範例

#include <bits/stdc++.h>
using namespace std;
#define lint long long int
#define endl '\n'

vector<vector<int>> graph(int(1e5), vector<int>());
vector<bool> visited(int(1e5), false);

struct BIT
{
    int n;
    vector<int> vec;

    BIT() : vec(int(1e5), 0) {}

    void init(int n)
    {
        this->n = n;
    }

    int lowbit(int x)
    {
        return x & (-x);
    }

    void add(int pos, int x)
    {
        for(; pos <= n ; pos += lowbit(pos)) vec[pos] += x;
    }

    int sum(int pos)
    {
        int ans = 0;
        for(; pos > 0 ; pos -= lowbit(pos)) ans += vec[pos];
        return ans;
    }
};
int main()
{
    int n; cin >> n;
    BIT bit;

    // initial
    bit.init(n);

    // use
    bit.add(2, 5);
    int sum = bit.sum(n);
}