連通性闆子

• 可達性 有向圖 邊雙縮點模版題
• Redundant Paths 無向圖 邊雙縮點
• [HAOI2006]受歡迎的牛 有向圖 邊雙縮點
• 嗅探器 無向圖 割點
• Network of Schools 有向圖，縮點，問形成強連通要幾條邊
• Cow Ski Area 不建圖，滑雪題

割點

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool g[MAX];

int cnt;
int dfn[MAX], low[MAX];
void tarjan(int u, int root){
    int flag = 0;//記錄子節點數量
    dfn[u] = low[u] = ++cnt;//更新時間戳
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v, root);
            low[u] = min(low[u], low[v]);//回溯更新low值
            if(low[v] >= dfn[u]){
                ++flag;
                if(u != root || flag > 1)g[u] = 1;//如果不是根節點或者是跟節點且子子點數量大于1就說明u是割點
            }
        }
        else low[u] = min(low[u], dfn[v]);//返祖邊
    }
}

for(int i = 1; i <= n; ++i){
        if(!dfn[i])tarjan(i, i);
		}
           

割邊

int tot;
int head[MAX];
struct ran{
    int to, nex;
    bool vis;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tim;
int bridge;
int dfn[NMAX], low[NMAX];
inline void tarjan(int u, int fa){
    dfn[u] = low[u] = ++tim;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(v == fa)continue;//如果是到父親節點就跳過
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
                ++bridge;//橋的數量
                tr[i].vis = tr[i ^ 1].vis = 1;//注意，标記的時候要标倆
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

for(int i = 1; i <= n; ++i)if(!dfn[i])tarjan(i, i);

    
    vector<pii>v;//因為題目要求從小到大，且u<=v
    for(int i = 0; i <= tot; i += 2){//注意是i+=2
        if(tr[i].vis){
            if(tr[i].to < tr[i ^ 1].to)v.push_back(m_p(tr[i].to, tr[i ^ 1].to));
            else v.push_back(m_p(tr[i ^ 1].to, tr[i].to));
        }
    }
    sort(v.begin(), v.end());
    cout<<bridge<<endl;
    for(int i = 0; i < v.size(); ++i){
        cout<<v[i].first<<" - "<<v[i].second<<endl;
    }
    cout<<endl;
}

void init(){//初始化
    mem(head, 0);
    mem(tr, 0);
    mem(dfn, 0);
    mem(low, 0);
    tot = -1;//必須是初始化為-1
    tim = bridge = 0;
}

           

點雙連通

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dfn[MAX], low[MAX];
int tim;//用于更新每個點的dfn
stack<int>st;
int cnt;//記錄點雙連通的數量
vector<int>bcc[MAX];//存點雙連通圖的點
void tarjan(int u, int fa){
    st.push(u);
    dfn[u] = low[u] = ++tim;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]){//u是割點
                ++cnt;//點雙數量+1
                bcc[cnt].push_back(u);//先把割點u扔進去
                while (st.top() != v) {//一直彈到v
                    bcc[cnt].push_back(st.top());
                    st.pop();
                }
                bcc[cnt].push_back(st.top());st.pop();//把v彈出
            }
        }
        else if(v != fa)low[u] = min(low[u], dfn[v]);//如果通路過了，就得判斷一下是不是返祖邊，而非父邊
    }
}

void work(){
    sdd(n, m);
    for(int i = 1; i <= m; ++i){
        sdd(a, b);
        add(a, b);
        add(b, a);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i, i);
        }
    }
    for(int i = 1; i <= cnt; ++i){
        for(int j = 0; j < bcc[i].size(); ++j)cout<<bcc[i][j]<<' ';
        cout<<endl;
    }
    
}

/*
 10 13
 1 2
 2 3
 3 5
 3 8
 4 8
 7 8
 8 9
 6 9
 6 10
 2 5
 1 4
 9 10
 8 10
 */
           

邊雙連通，縮點

int n, m;
int a, b;

int tot = 1;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dfn[MAX], low[MAX];
int tim;
stack<int>st;
int cnt;
bool vis[MAX];
bool g[MAX];
int color[MAX];
void tarjan(int u){
    dfn[u] = low[u] = ++tim;
    st.push(u);
    vis[u] = 1;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(g[i])continue;
        g[i] = g[i ^ 1] = 1;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        ++cnt;
        int now;
        do {
            now = st.top();
            st.pop();
            vis[now] = 0;
            color[now] = cnt;
        } while (now != u);
    }
}

int in[MAX];

void work(){
    sdd(n, m);
    for(int i = 1; i <= m; ++i){
        sdd(a, b);
        add(a, b);
        add(b, a);
    }
    for(int i = 1; i <= n; ++i)if(!dfn[i])tarjan(i);
    for(int u = 1; u <= n; ++u){
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(color[u] != color[v]){//根據需要連邊
              
            }
        }
    }

}