并查集

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
    class Program
    {
        private static int[] gx;
        private static int userNum = 100000;
        public static void Main()
        {
            gx = new int[userNum + 1];

            //生成初始数组 gx[i] = i;
            for (int i = 0; i <= userNum; i++)
            {
                gx[i] = i;
            }

            //连通
            StreamReader sr = new StreamReader(@"144341511030664.txt", Encoding.Default);
            String strLine = null;
            String[] arrStr = null;
            while ((strLine = sr.ReadLine()) != null)
            {
                arrStr = strLine.Split(' ');
                int xr = FindRoot(int.Parse(arrStr[0]));
                int yr = FindRoot(int.Parse(arrStr[1]));
                //如果不是同一个根节点则合并
                if (xr != yr)
                {
                    gx[yr] = xr;
                }
            }

            //计数 gx[i]=i 则是根节点
            for (int i = 1; i <= userNum; i++)
            {
                if (gx[i] == i)
                {
                    gx[0]++;
                }
            }
            Console.WriteLine(gx[0]);
            Console.Read();
        }


        private static int FindRoot(int x)
        {
            int r = x, j;
            while (gx[r] != r)//如果不是根节点 则继续上推
            {
                r = gx[r];
            }
            //此时r为根节点
            while (gx[x] != r)//压缩路径 所有非根节点直接指向根节点
            {
                j = gx[x];
                gx[x] = r;
                x = j;
            }
            return r;
        }
    }
}