Submission #7066417

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static void Swap<T>(ref T a, ref T b)
    {
	var t = a;
	a = b;
	b = t;
    }

    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class UnionFind
{
    private int[] d;

    public UnionFind(int n)
    {
	d = new int[n];
	for (int i = 0; i < n; i++){ d[i] = -1; }
    }

    public int Find(int x)
    {
	if (d[x] < 0){ return x; }
	return d[x] = Find(d[x]);
    }

    public void Unite(int x, int y)
    {
	x = Find(x); y = Find(y);
	if (x == y){ return; }
	if (d[x] > d[y]){ Swap(ref x, ref y); }
	d[x] += d[y];
	d[y] = x;
    }

    public bool Same(int x, int y){ return Find(x) == Find(y); }
    public int Size(int x){ return -d[Find(x)]; }
}

class Program
{
    public static void Main()
    {
	var tmp = ReadIntArray();
	int n = tmp[0], k = tmp[1], l = tmp[2];

	UnionFind uf1 = new UnionFind(n+1);
	
	for (int i = 0; i < k; i++)
	{
	    tmp = ReadIntArray();
	    int p = tmp[0], q=tmp[1];
	    uf1.Unite(p, q);
	}

	UnionFind uf2 = new UnionFind(n+1);

	for (int i = 0; i < l; i++)
	{
	    tmp = ReadIntArray();
	    int r = tmp[0], s = tmp[1];
	    if (uf1.Same(r, s)){
		uf2.Unite(r,s);
	    }
	}

	for (int i = 1; i <= n; i++)
	{
	    Write(uf2.Size(i));
	    if (i!=n){ Write(" "); }
	}
	WriteLine("");
    }
}

Submission Info

Judge Result