# Connectively
# 無向圖連通性
## 邊、一些定義
**樹邊(tree edge)**：真正在樹上的邊，由父親連到小孩
**回邊(back edge)**：子孫連回祖先
**前向邊(front edge)**：連到子孫的邊(不是樹)邊
**交錯邊(cross edge)**：連到非直系子孫
**內節點**:非根節點與葉節點(也就是說他至少會連兩個邊!)

**橋**：拔掉此邊後連通塊加1
**割點/關節點**：拔點此點後連通塊加1
**邊雙連通分量**：在此連通塊內拔掉任何一條邊仍然是連通塊，即連通塊內無橋
* **注意!**
以點為主體，可能有邊不在任何集合內

**點雙連通分量(BCC)**：在此連通塊內拔掉任何一條點仍然是連通塊，即連通塊內無割點
* **注意!**
以點為主體，可能同一點在不同集合內

* 性質
1. u到v定存在兩條不重複路徑
2. 對於u, v, w，存在由u到v再到w的簡單路徑(由1可以推得)
3. 對於任兩條邊，在同一簡單環上，則若且唯若他們屬於同點雙連通分量
## Tarjan(塔樣?)

定義low函數為不經過**父節點**所可以抵達的最淺深度
* u還沒走過:
u會是v的小孩
從u點走，回傳low(u)看是否比目前小(可能透過回邊走到祖先)
* u走過
(v, u)會是一條回邊，檢查depth(u)是否比low(v)小，是的話更新

* **找橋**：如果depth[v] = low[v]，則父邊就會是橋
代表 v 在不依靠父邊的情況下永遠沒辦法走到它的祖先，此時v的父邊就會是橋

void dfs(int v, int p)
{
    visited[v] = 1;
    if (v != p) // not root 
        low[v] = depth[p]+1;
    
    for (int u: adj[v])
    {
        if (u == p) continue;
        if (visited[u])
        {
            if (depth[u] < low[v]) low[v] = depth[u];
        }
        else
        {
            dfs(u);
            if (low[u] < low[v]) low[v] = low[u];
        }
    }
    if (low[v] == depth[v])
    {
        // (p, v) = bridge if v is not a root vertex
    }
    
}

* **找割點/關節點**：
如果v的子孫們沒有除了透過v到達祖先的方法,v為關節點
**v為root時**，若child >= 2 ，root為關節點

question:為何不能改為判斷式為 low[u] >= dis[u]
A: 可能繞回來的點恰好是關節點，遇上這情況會誤判

void dfs(int v, int p)
{
    visited[v] = 1;
    if (v!=p) low[v] = depth[p]+1;
    int chd_cnt = 0;
    for (int u:adj[v])
    {
        if (u==p) continue;
        if (!visited[u])
        {
            chd_cnt++, dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] >= dis[v] && p!=-1)
                //v is a non-root cut-vertex
        }
        else if (dfs[u] < dfs[v])
            low[v] = min(low[v], dis[u]); 
    }
    if (p==-1 && chd_cnt > 1) 
        //the root of the tree is a cut-vertex
}
    

* **找邊雙連通分量**
在遞迴的過程

void dfs(int v, int p)
{
    visited[v] = 1;
    if (v != p) // not root 
        low[v] = depth[p]+1;
    stack<int> stk;
    stk.push(v);
    for (int u: adj[v])
    {
        if (v==p) continue;
        if (!visited[u])
        {
            dfs(v, u);
            low[v] = min(low[v], low[u]);
            if (low[v] > dis[u])
            {
                bcc_cnt++;
                while(stk.top()!=p)
                    bcc[bcc_cnt].push_back(stk.top())
            }
        }
    }
}

* **找點雙連通分量**

## 例題
### Cycling city
給一張無向圖，是否有(a, b)可以有三種之間可以有三組路徑(點不重複、邊不重複)

# 有向圖連通性

## 強連通分量
在此連通塊中每一個點都可以到別的點，可以**縮點**之後變成**DAG(有向無環圖)!**

## Kosaraju

## 2-SAT問題
Q：為甚麼不是無向圖?
如果(a或b)的話，若a是True，但b可能是true或false，所以是有向!(若你知道一個是false，另一個一定是True!)

建立¬a -> b, ¬b -> a的邊
接著用Kosaraju做!