Luogu P2661 – 并查集

PROBLEM

https://www.luogu.org/problemnew/show/P2661

ANALYSIS

找到有向图中最小的环。n个点，n条边，n<2*10^5。

SOLUTION

首先是两种弱智模拟做法，STL真的降智。

TLE, 80

//80
//STL sucks
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 202000;
int n, cnt;
int d[N];
struct Status {
    int root, now, cnt;
    Status() {}
    Status(int a, int b, int c): root(a), now(b), cnt(c) {}
};
queue<Status> q;

int main() {
    cin >> n;
    for (int i = 1, t; i <= n; i++) {
        cin >> t;
        d[i] = t;
        q.push(Status(i, t, 0));
    }
    Status u;
    while (1) {
        u = q.front();
        if (u.root == u.now) {
            cout << u.cnt << endl;
            return 0;
        }
        q.push(Status(u.root, d[u.now], u.cnt + 1));
        q.pop();
    }
    return 0;
}

TLE, 80

//80
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 202000;
int n, cnt;
int d[N], c[N];

int main() {
    cin >> n;
    for (int i = 1, t; i <= n; i++) {
        scanf("%d", &t);
        c[i] =  d[i] = t;
    }
    for (cnt = 1;; cnt++) {
        for (int i = 1; i <= n; i++) {
            if(c[i]==i){
                cout<<cnt<<endl;
                return 0;
            }
            c[i]=d[c[i]];
        }
    }
    return 0;
}

比较常规的正确做法：使用并查集，这里算并查集的时候要算一下距离祖先的距离。或许这就是这道题唯一要注意一下的点了吧。

AC

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 202000, inf = 0x7fffffff;
int n, ans = inf;
int f[N], d[N];

int getanc(int x) {
    if (x == f[x]) {
        return x;
    }
    int u = f[x];
    f[x] = getanc(f[x]);
    if (u != f[x]) {
        d[x] += d[u];
    }
    return f[x];
}

int main() {
    cin >> n;
    for (int i = 1, t; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 1, t, a, b; i <= n; i++) {
        scanf("%d", &t);
        a = getanc(i);
        b = getanc(t);
        if (a != b) {
            f[a] = b;
            d[i] = d[t] + 1;
        } else {
            ans = min(ans, d[i] + d[t] + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

REFERENCE

1. https://www.luogu.org/problemnew/show/P2661

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.