Submission #16319699

---

Source Code Expand

// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on
void main()
{
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long M;
    M = input.front.to!long;
    input.popFront;

    long[] A = new long[](cast(size_t)(M));
    long[] B = new long[](cast(size_t)(M));
    foreach (i; 0 .. cast(size_t)(M))
    {
        A[i] = input.front.to!long;
        input.popFront;
        B[i] = input.front.to!long;
        input.popFront;
    }

    solve(N, M, A, B);
}

void solve(long N, long M, long[] A, long[] B)
{
    auto uf = UnionFind(N);
    A[] -= 1;
    B[] -= 1;
    foreach (i; 0 .. M)
    {
        uf.unite(A[i], B[i]);
    }
    long ans;
    foreach (i; 0 .. N)
    {
        ans = ans.max(uf.size(i));
    }
    writeln(ans);
}

struct UnionFind
{
    alias T = long;
    T[] rank, parent, sizes;
    this(T n)
    {
        rank = new T[](n);
        sizes = new T[](n);
        sizes[] = 1;
        parent = iota!T(n).array();
    }

    T find(T x)
    {
        return (this.parent[x] == x) ? x : (this.parent[x] = this.find(this.parent[x]));
    }

    void unite(T x, T y)
    {
        T rx = this.find(x), ry = this.find(y);
        if (rx == ry)
            return;
        this.sizes[rx] = this.sizes[ry] = this.sizes[rx] + this.sizes[ry];
        if (this.rank[rx] == this.rank[ry])
            this.parent[rx] = ry, this.rank[ry]++;
        else if (this.rank[rx] < this.rank[ry])
            this.parent[rx] = ry;
        else
            this.parent[ry] = rx;
    }

    T size(T x)
    {
        return this.sizes[this.find(x)];
    }
}

Submission Info

Judge Result