⑴ 涓嶇浉浜ら泦 (disjointSet)
鍦ㄦ暟鎹緇撴瀯鐨勫囧欎笘鐣岄噷錛DisjointSet錛堜笉鐩鎬氦闆嗭級</錛屽傚悓涓搴фˉ姊侊紝榪炴帴鐫鍏冪礌鐨勭瓑浠峰叧緋匯傚畠鐨勬牳蹇冩搷浣滐紝Find鍜孶nion錛岀姽濡傛帰緔㈣糠瀹鐨勬寚鍗楅拡錛屽紩棰嗘垜浠鐞嗚В闆嗗悎鐨勫悎騫朵笌鏌ユ壘銆備粖澶╋紝鎴戜滑灝嗘洿娣卞叆鍦版帰緔㈠叾涓鐨刄nion榪愮畻錛屽挨鍏舵槸濡備綍浼樺寲Find鎿嶄綔錛屾彁鍗囨晥鐜囥
鎯寵薄涓涓嬶紝姣忎釜鍏冪礌灝卞儚涓涓鐙鐗圭殑瀛楁瘝錛岃孌isjointSet鏄鎴戜滑鐨勫瓧姣嶈〃錛岄氳繃涓嬫爣鏉ユ爣璁版瘡涓鍏冪礌鎵灞炵殑闆嗗悎銆傚綋閬囧埌Find鎿嶄綔鏃訛紝鎴戜滑鐨勭洰鏍囨槸鎵懼嚭瀛楁瘝x鎵鍦ㄧ殑瀛楁瘝琛ㄣ傚叧閿鍦ㄤ簬錛屾垜浠鍏蟲敞鐨勪笉鏄鍝涓瀛楁瘝鏄鍝涓錛岃屾槸瀹冧滑鏄鍚﹀叡浜鍚屼竴涓瀛楁瘝琛錛岃繖涓鐐瑰湪Find(a)==Find(b)鐨勭瓑寮忎腑寰椾互浣撶幇銆
綆鍗曞湴鍚堝苟涓や釜闆嗗悎錛Union鎿嶄綔</鍙鑳芥樉寰楃洿瑙傦紝浣嗗綋鎴戜滑瑕侀珮鏁堝湴澶勭悊澶ч噺鍏冪礌鏃訛紝闂棰樺氨鍑虹幇浜嗐傛瘮濡傦紝濡傛灉鐩存帴鎵ц孶nion(4,5)錛屽彲鑳戒細瀵艱嚧娣卞害鏌ユ壘錛孎ind鐨勬ц兘鐡墮堢敱姝ゆ樉鐜般備負浜嗚В鍐寵繖涓闂棰橈紝鎴戜滑寮曞叆浜嗘寜澶у皬鍜岄珮搴﹁繘琛屽悎騫剁殑絳栫暐銆
鎸夊ぇ灝忔眰騫</鐨勬敼榪涚増涓錛屾垜浠閫氳繃姣旇緝闆嗗悎鐨勫ぇ灝忔垨楂樺害鏉ュ喅瀹氬悎騫剁殑鏂瑰悜錛岄伩鍏嶄笉蹇呰佺殑閫掑綊銆傝繖鏍鳳紝鍗充嬌澶氭℃墽琛孶nion錛孎ind(8)鐨勬煡鎵炬椂闂翠篃浼氭樉钁楃緝鐭銆傝璺寰勫帇緙榪欎竴絳栫暐錛屽氨鏄鍦‵ind鎿嶄綔涓娣誨姞鑱鏄庣殑浼樺寲錛屼嬌寰楁瘡嬈℃煡鎵鵑兘灝介噺鍑忓皯灞傜駭錛屽ぇ澶ф彁楂樻晥鐜囥
璺寰勫帇緙╀笌鎸夊ぇ灝忔眰騫舵槸鐩歌緟鐩告垚鐨勶紝瀹冧滑鍏卞悓鎻愬崌浜嗙畻娉曠殑鎬ц兘銆傜劧鑰岋紝璺寰勫帇緙</涓鎸夐珮搴︽眰騫騫朵笉瀹屽叏鍏煎癸紝鍥犱負鍘嬬緝鍚庣殑緇撴瀯闅愯棌浜嗛珮搴︿俊鎮錛岃繖鍦ㄥ悓鏃朵嬌鐢ㄦ椂闇瑕佽皚鎱庡勭悊錛屾湁鏃朵細鍒╃敤涓涓浼拌″礆紝濡傜З錛屾潵杈呭姪鍐崇瓥銆
鍦ㄨ繖涓鎺㈢儲鏃呯▼涓錛屾垜浠涓嶆柇浼樺寲錛岃拷奼傛晥鐜囦笌綺劇『鎬х殑騫寵銆傞氳繃鐞嗚ВDisjointSet鐨勬瘡涓緇嗚妭錛屾垜浠涓嶄粎鑳借В鍐沖疄闄呴棶棰橈紝鏇磋兘棰嗙暐鏁版嵁緇撴瀯鐨勫閥濡欎箣澶勩傝╂垜浠涓璧峰湪浠ｇ爜鐨勪笘鐣屼腑錛岄嗙暐FindUnion綆楁硶鐨勭簿榪涗笌欖呭姏鍚э紒