tarjan学习笔记

小咪咪 2021-10-30 05:56 300阅读 0赞

1.$tarjan$求强连通分量

思想：在$dfs$的过程中，把强连通分量中的点入栈，当找到一个强连通分量的最起始的点，就将其所在强连通分量中的点出栈。

缩点

把强连通分量中的点缩成一个点，进行重新建图，从而解决一些问题。

2.割点  
若将这个点在图中所连的边删去，图变得不连通，则称这个点为一个割点。

考虑两种情况：

若节点$x$为根节点，则它若联结着两颗及以上数量的子树，则$x$为割点。

$otherwise$，设$x$的其中一个儿子为$v$，若出现$low\[v\] \\ge dfn\[x\]$，则$x$为割点。

3.习题

luogu 3388 【模板】割点（割顶）

#include <bits/stdc++.h>
    const int MAXN = 20050;
    const int MAXM = 100050;
    using namespace std;
    struct node {
        int to, nextt;
    }edge[MAXM << 1];
    int n, m, u, v, num, cnt, low[MAXN], dfn[MAXN], head[MAXN];
    set<int> s;
    void addedge(int u, int v) {
        edge[++num].to = v;
        edge[num].nextt = head[u];
        head[u] = num;
    }
    void tarjan(int x, int fa) {
        dfn[x] = low[x] = ++cnt;
        int child = 0;
        for(int i = head[x]; i; i = edge[i].nextt) {
            int to = edge[i].to;
            if(!dfn[to]) {
                if(x == fa)
                    child++;
                tarjan(to, x);
                low[x] = min(low[x], low[to]);
                if(x != fa && low[to] >= dfn[x])
                    s.insert(x);
            }
            low[x] = min(low[x], dfn[to]);
        }
        if(x == fa && child >= 2)
            s.insert(x);
    }
    int main() {
        cin >> n >> m;
        for(int i = 1; i <= m; i++) {
            cin >> u >> v;
            addedge(u, v);
            addedge(v, u);
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i, i);
        }
        cout << (int)s.size() << endl;
        for(set<int>::iterator it = s.begin(); it != s.end(); it++)
            cout << *it << " ";
        cout << endl;
        return 0;
    }

Luogu 2921 Trick or Treat on the Farm

第一种做法是进行$tarjan$，对于所在强连通分量里个数大于$1$的点，答案即为当前强连通分量的大小；由于数据的特殊性，另一种情况即为到强连通分量的距离加上那个强连通分量的大小。

第二种做法是三遍递归。第一遍把所有不在环内的点打上标记，第二遍求出未被标记的点所在环的大小，第三遍累加到环的距离。总体想法与第一种是一样的。

代码(\#2)：

#include <bits/stdc++.h>
    const int MAXN = 100050;
    using namespace std;
    int n, x, nextt[MAXN], ans[MAXN], in[MAXN];
    bool vis[MAXN];
    void dfs1(int x) {
        vis[x] = true;
        if(!--in[nextt[x]])
            dfs1(nextt[x]);
    }
    int dfs2(int x, int num) {
        vis[x] = true;
        ans[x] = num;
        if(ans[nextt[x]])    
            return num;
        return ans[x] = dfs2(nextt[x], num + 1);
    }
    int dfs3(int x) {
        if(ans[x])
            return ans[x];
        return ans[x] = dfs3(nextt[x]) + 1;
    }
    int main() {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            cin >> nextt[i];
            ++in[nextt[i]];
        }
        for(int i = 1; i <= n; i++) {
            if(!vis[i] && !in[i])
                dfs1(i);
        }
        for(int i = 1; i <= n; i++) {
            if(!ans[i] && in[i])
                x = dfs2(i, 1);
        }
        for(int i = 1; i <= n; i++) {
            if(!ans[i] && !in[i])
                x = dfs3(i);
        }
        for(int i = 1; i <= n; i++)
            cout << ans[i] << endl;
        return 0;
    }

Luogu 1726 上白泽慧音

显然答案即为最大的强连通分量的个数。

#include <bits/stdc++.h>
    const int MAXN = 5050;
    const int MAXM = 50050;
    const int INF = 1 << 30;
    using namespace std;
    stack<int> s;
    struct Edge {
        int to , nextt;
    }edge[MAXM << 1];
    int n, m, u, v, ty, num, cnt, cnt1, Max, pos, ss[MAXN], head[MAXN], low[MAXN], dfn[MAXN], sccno[MAXN];
    void addedge(int u, int v) {
        edge[++num].to = v;
        edge[num].nextt = head[u];
        head[u] = num;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        s.push(x);
        for(int i = head[x]; i; i = edge[i].nextt) {
            int to = edge[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) {
            int now, cnt2 = 0;
            ++cnt1;
            while(true) {
                now = s.top();
                s.pop();
                ++cnt2;
                sccno[now] = cnt1;
                ss[now] = cnt1;
                if(now == x)
                    break;
            }
            if(cnt2 > Max) {
                Max = cnt2;
                pos = cnt1;
            }
        }
    }
    int main() {
        cin >> n >> m;
        for(int i = 1; i <= m; i++) {
            cin >> u >> v >> ty;
            addedge(u, v);
            if(ty == 2)
                addedge(v, u);
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        cout << Max << endl;
        for(int i = 1; i <= n; i++) {
            if(ss[i] == pos) {
                for(int j = i; j <= n; j++) {
                    if(ss[j] == pos)
                        cout << j << " ";
                }
                return 0;
            } 
        }
        return 0;
    }

Luogu 3387 【模板】缩点

先进行缩点，后作类似拓扑的操作，$dp$即可。

#include <bits/stdc++.h>
    const int MAXN = 10050;
    const int MAXM = 100050;
    using namespace std;
    stack<int> ss;
    queue<int> q;
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXM];
    struct Edge2 {
        int u, to, nextt;
    }edge2[MAXN];
    int n, m, u, v, ans, num1, num2, cnt, cnt1, head1[MAXN], head2[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN], sd[MAXN], in[MAXN], val[MAXN], dis[MAXN];
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void addedge2(int u, int v) {
        edge2[++num2].u = u;
        edge2[num2].to = v;
        edge2[num2].nextt = head2[u];
        head2[u] = num2;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        ss.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) {
            ++cnt1;
            while(true) {
                int now = ss.top();
                ss.pop();
                sccno[now] = cnt1;
                sd[now] = x;
                if(now == x)
                    break;
                val[x] += val[now];            
            }
        }
    }
    void topo() {
        for(int i = 1; i <= n; i++) {
            if(!in[i] && sd[i] == i) {
                q.push(i);
                dis[i] = val[i];
            }
        }
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(int i = head2[now]; i; i = edge2[i].nextt) {
                int to = edge2[i].to;
                dis[to] = max(dis[to], dis[now] + val[to]);
                if(!--in[to])
                    q.push(to);
            }
        }
        for(int i = 1; i <= n; i++)
            ans = max(ans, dis[i]);
    }
    int main() {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            cin >> val[i];
        for(int i = 1; i <= m; i++) {
            cin >> u >> v;
            addedge1(u, v);
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i = 1; i <= m; i++) {
            int u = sd[edge1[i].u], v = sd[edge1[i].to];
            if(u == v)
                continue;
            addedge2(u, v);
            in[v] ++;
        }
        topo();
        cout << ans << endl;
        return 0;
    }

Luogu 3627 抢掠计划

先缩点，后跑一遍$spfa$（最长路）即可。

#include <bits/stdc++.h>
    const int MAXN = 500050;
    const int INF = 1 << 30;
    using namespace std;
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXN];
    struct Edge2 {
        int u, to, val, nextt;
    }edge2[MAXN];
    stack<int> d;
    queue<int> q;
    int n, m, u, v, w, x, num1, num2, cnt, cnt1, s, p, ans, sd[MAXN], head1[MAXN], head2[MAXN], low[MAXN], dfn[MAXN], vall[MAXN], dis[MAXN], sccno[MAXN];
    bool vis[MAXN];
    int read() {
        int x = 0;
        bool sign = false;
        char alpha = 0;
        while(!isdigit(alpha)) {
            sign |= alpha == '-';
            alpha = getchar();
        }
        while(isdigit(alpha)) {
            x = (x << 1) + (x << 3) + (alpha ^ 48);
            alpha = getchar();
        }
        return sign ? -x : x;
    }
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void addedge2(int u, int v, int w) {
        edge2[++num2].u = u;
        edge2[num2].to = v;
        edge2[num2].val = w;
        edge2[num2].nextt = head2[u];
        head2[u] = num2;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        d.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) { 
            ++cnt1;
            while(true) {
                int now = d.top();
                d.pop();
                sccno[now] = cnt1;
                sd[now] = x;
                if(x == now)
                    break;
                vall[x] += vall[now];
            }
        }
    }
    void spfa() {
        dis[sd[s]] = vall[sd[s]];
        q.push(sd[s]);
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            vis[now] = false;
            for(int i = head2[now]; i; i = edge2[i].nextt) {
                int to = edge2[i].to, val = edge2[i].val;
                if(dis[to] < dis[now] + val) {
                    dis[to] = dis[now] + val;
                    if(!vis[to]) {
                        vis[to] = true;
                        q.push(to);
                    }
                }
            }
        }    
    }
    int main() {
        n = read();
        m = read();
        for(int i = 1; i <= m; i++) {
            u = read();
            v = read();
            addedge1(u, v);
        }
        for(int i = 1; i <= n; i++)
            vall[i] = read();
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i = 1; i <= m; i++) {
            u = sd[edge1[i].u];
            v = sd[edge1[i].to];
            w = vall[v];
            if(u == v)
                continue;
            addedge2(u, v, w);
        }
        s = read();
        p = read();
        spfa();
        for(int i = 1; i <= p; i++) {
            x = read();
            ans = max(ans, dis[sd[x]]);
        }
        cout << ans << endl;
        return 0;
    }

Luogu 2002 消息扩散

答案显然是缩点后入度为$0$的点的个数。

#include <bits/stdc++.h>
    const int MAXN = 100050;
    const int MAXM = 500500;
    using namespace std;
    stack<int> ss;
    int n, m, u, v, pos, num, num1, num2, cnt, cnt1, in[MAXN], head1[MAXN], head2[MAXN], low[MAXN], dfn[MAXN], sd[MAXN], sccno[MAXN];
    bool vis[5050][5050];
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXM];
    struct Edge2 {
        int u, to, nextt;
    }edge2[MAXM];
    int read() {
        int x = 0;
        bool sign = false;
        char alpha = 0;
        while(!isdigit(alpha)) {
            sign |= alpha == '-';
            alpha = getchar();
        }
        while(isdigit(alpha)) {
            x = (x << 1) + (x << 3) + (alpha ^ 48);
            alpha = getchar();
        }
        return sign ? -x : x;
    }
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void addedge2(int u, int v) {
        edge2[++num2].u = u;
        edge2[num2].to = v;
        edge2[num2].nextt = head2[u];
        head2[u] = num2;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        ss.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) {
            ++cnt1;
            while(true) {
                int now = ss.top();
                ss.pop();
                sccno[now] = cnt1;
                sd[now] = cnt1;
                if(now == x)
                    break;        
            }
        }
    }
    int main() {
        n = read(); 
        m = read();
        for(int i = 1; i <= m; i++) {
            u = read();
            v = read();
            if(u == v)
                continue;
            addedge1(u, v);
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i = 1; i <= num1; i++) {
            u = sd[edge1[i].u];
            v = sd[edge1[i].to];
            if(u == v)
                continue;
            in[v]++;
            addedge2(u, v);
        }
        for(int i = 1; i <= cnt1; i++) {
            if(!in[i])
                num++;
        }
        cout << num << endl;
        return 0;
    }

Luogu 2746 Network of Schools

第一问的答案显然是缩点后入度为$0$的点的个数。

对于第二问，若存在出度为$0$的点或者入度为$0$的点则不满足条件。若把一个出度为$0$的点与一个入度为$0$的点连一条边，问题便迎刃而解。

考虑到两种点的个数不一定相同，选取其中的最大值即可。

记得判断是一个大环的情况。

#include <bits/stdc++.h>
    const int MAXN = 250000;
    using namespace std;
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXN << 1];
    struct Edge2 {
        int u, to, nextt;
    }edge2[MAXN << 1];
    stack<int> s;
    int n, u ,v, cnt, cnt1, ans1, num, num1, num2, head1[MAXN], head2[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN], sd[MAXN], in[MAXN], out[MAXN];
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void addedge2(int u, int v) {
        edge2[++num2].u = u;
        edge2[num2].to = v;
        edge2[num2].nextt = head2[u];
        head2[u] = num2;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        s.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(low[x] == dfn[x]) {
            ++cnt1;
            while(true) {
                int now = s.top();
                s.pop();
                sd[now] = cnt1;
                sccno[now] = cnt1;
                if(now == x)
                    break;
            }
        }
    }
    int main() {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            while(scanf("%d", &v) == 1) {
                if(v == 0)
                    break;
                addedge1(i, v);
            }
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i = 1; i <= num1; i++) {
            u = sd[edge1[i].u];
            v = sd[edge1[i].to];
            if(u == v)
                continue;
            addedge2(u, v);
            in[v]++;
            out[u]++;
        }
        for(int i = 1; i <= cnt1; i++) {
            if(in[i] == 0)
                ans1++;
            if(out[i] == 0)
                num++;
        }
        cout << ans1 << endl;
        if(cnt1 == 1) {
            cout << "0" << endl;
            return 0;
        }
        cout << max(num, ans1) << endl;
        return 0;
    }

Luogu 2341 受欢迎的牛

若出现个数 \\ge 1的出度为$0$的强连通分量，则无解。

$otherwise$答案即为出度为$0$的强连通分量的大小。

#include <bits/stdc++.h>
    const int MAXN = 10050;
    const int MAXM = 50050;
    using namespace std;
    stack<int> ss;
    int n, m, u, v, pos, num, num1, num2, cnt, cnt1, head1[MAXN], head2[MAXN], low[MAXN], dfn[MAXN], sd[MAXN], f[MAXN], sccno[MAXN];
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXM];
    struct Edge2 {
        int u, to, nextt;
    }edge2[MAXM];
    int read() {
        int x = 0;
        bool sign = false;
        char alpha = 0;
        while(!isdigit(alpha)) {
            sign |= alpha == '-';
            alpha = getchar();
        }
        while(isdigit(alpha)) {
            x = (x << 1) + (x << 3) + (alpha ^ 48);
            alpha = getchar();
        }
        return sign ? -x : x;
    }
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void addedge2(int u, int v) {
        edge2[++num2].u = u;
        edge2[num2].to = v;
        edge2[num2].nextt = head2[u];
        head2[u] = num2;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        ss.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) {
            ++cnt1;
            while(true) {
                int now = ss.top();
                ss.pop();
                sccno[now] = cnt1;
                sd[now] = cnt1;
                f[cnt1] ++;
                if(now == x)
                    break;        
            }
        }
    }
    int main() {
        n = read(); 
        m = read();
        for(int i = 1; i <= m; i++) {
            u = read();
            v = read();
            addedge1(u, v);
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i = 1; i <= m; i++) {
            u = sd[edge1[i].u];
            v = sd[edge1[i].to];
            if(u == v)
                continue;
            addedge2(u, v);
        }
        for(int i = 1; i <= cnt1; i++) {
            if(!head2[i]) {
                pos = i;
                num++;
            }
            if(num == 2) {
                cout << "0" << endl;
                return 0;
            }
        }
        cout << f[pos] << endl;
        return 0;
    }

Luogu 1262 间谍网络

考虑无解的情况。若存在一个点既不能被贿赂，也没有入度，则不存在答案。

先缩点。对于现在没有入度且原先在强连通分量中的点，代价即为这些点中花费最小的值，累加即可。

#include <bits/stdc++.h>
    const int MAXN = 100050;
    const int INF = 1 << 30;
    int n, m, u, v, p, num1, num2, cnt, cnt1, ans, in[MAXN], dfn[MAXN], low[MAXN], head1[MAXN], head2[MAXN], sccno[MAXN], val[MAXN], vall[MAXN], sd[MAXN];
    using namespace std;
    stack<int> s;
    struct Edge1 {
        int u, to, nextt;
    }edge1[MAXN];
    int read() {
        int x = 0;
        bool sign = false;
        char alpha = 0;
        while(!isdigit(alpha)) {
            sign |= alpha == '-';
            alpha = getchar();
        }
        while(isdigit(alpha)) {
            x = (x << 1) + (x << 3) + (alpha ^ 48);
            alpha = getchar();
        }
        return sign ? -x : x;
    }
    void addedge1(int u, int v) {
        edge1[++num1].u = u;
        edge1[num1].to = v;
        edge1[num1].nextt = head1[u];
        head1[u] = num1;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++cnt;
        s.push(x);
        for(int i = head1[x]; i; i = edge1[i].nextt) {
            int to = edge1[i].to;
            if(!dfn[to]) {
                tarjan(to);
                low[x] = min(low[x], low[to]);
            }
            else if(!sccno[to])
                low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]) {
            ++cnt1;
            while(true) {
                int now = s.top();
                s.pop();
                sd[now] = cnt1;
                sccno[now] = cnt1;
                vall[cnt1] = min(vall[cnt1], val[now]);
                if(now == x)
                    break;
            }
        }
    }
    int main() {
        n = read();
        p = read();
        for(int i = 1; i <= n; i++)
            val[i] = vall[i] = INF;
        for(int i = 1; i <= p; i++) {
            u = read();
            val[u] = read();
        }
        m = read();
        for(int i = 1; i <= m; i++) {
            u = read();
            v = read();
            in[v]++;
            addedge1(u, v);
        }
        for(int i = 1; i <= n; i++) {
            if(val[i] == INF && in[i] == 0) {
                cout << "NO" << endl << i << endl;
                return 0;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i] && val[i] != INF)
                tarjan(i);
        }
        for(int i = 1; i <= n; i++)
            in[i] = 0;
        for(int i = 1; i <= num1; i++) {
            u = sd[edge1[i].u];
            v = sd[edge1[i].to];
            if(u == v)
                continue;
            in[v]++;
        }
        for(int i = 1; i <= cnt1; i++) {
            if(in[i] == 0)
                ans += vall[i];
        }
        cout << "YES" << endl << ans << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/BeyondLimits/p/11253239.html