package Ġcom . mr xy x . algorithm Ċ Ċ /** Ċ Ġ* Ġ å¹¶ æŁ¥ éĽĨ Ġ ç®Ĺæ³ķ Ċ Ġ*/ Ċ class ĠUnion Find Alg Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ å¹¶ æŁ¥ éĽĨ æŁ¥è¯¢ ç®Ĺæ³ķ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġinternal Ġclass ĠU F ( private Ġvar Ġcount : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ åŃĺåĤ¨ èĭ¥ å¹² æ£ µ æłĳ ĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġparent Ġ= ĠInt Array ( count ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġ è®°å½ķ æłĳ çļĦ âĢľ éĩį éĩı âĢĿ ĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġsize Ġ= ĠInt Array ( count ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġå°Ĩ Ġp ĠåĴĮ Ġq Ġ è¿ŀ éĢļ ĊĠĠĠĠĠĠĠĠ Ġ* Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġunion ( p : ĠInt , Ġq : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot P Ġ= Ġfind ( p ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot Q Ġ= Ġfind ( q ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root P Ġ== Ġroot Q ) Ġreturn ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ä¼ĺåĮĸ çĤ¹ Ġå°ı æłĳ æİ¥ åĪ° å¤§ æłĳ ä¸ĭéĿ¢ ï¼Į è¾ĥ å¹³ è¡¡ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( size [ root P ] Ġ> Ġsize [ root Q ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ root Q ] Ġ= Ġroot P ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize [ root P ] Ġ+= Ġsize [ root Q ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ root P ] Ġ= Ġroot Q ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize [ root Q ] Ġ+= Ġsize [ root P ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcount -- ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠåĪ¤æĸŃ Ġp ĠåĴĮ Ġq Ġæĺ¯åĲ¦ äºĴ çĽ¸ è¿ŀ éĢļ ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġconnected ( p : ĠInt , Ġq : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot P Ġ= Ġfind ( p ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot Q Ġ= Ġfind ( q ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ å¤Ħ äºİ åĲĮ ä¸Ģ æ£ µ æłĳ ä¸ĬçļĦ èĬĤçĤ¹ ï¼Į çĽ¸ äºĴ è¿ŀ éĢļ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot P Ġ== Ġroot Q ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* Ġè¿ĶåĽŀ èĬĤçĤ¹ Ġx ĠçļĦ æł¹ èĬĤçĤ¹ ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġfind ( x : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġx ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( parent [ x ] Ġ!= Ġx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ä¼ĺåĮĸ çĤ¹ Ġ è¿Ľè¡Į è·¯å¾Ħ åİĭç¼© ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ x ] Ġ= Ġparent [ parent [ x ]] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġparent [ x ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġx ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġcount ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent [ i ] Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize [ i ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ çŃī å¼ı æĸ¹ ç¨ĭ çļĦ åı¯ æ»¡è¶³ æĢ§ ĊĠĠĠĠ Ġ* Ġhttps :// leetcode - cn . com / problems / s atis fi ability - of - equality - equ ations / ĊĠĠĠĠ Ġ* Ġstep Ġ 1 ãĢģ å°Ĩ equ ations ä¸ŃçļĦ ç®Ĺ å¼ı æł¹æį® == åĴĮ != åĪĨ æĪĲ ä¸¤ éĥ¨åĪĨ ï¼Į ĊĠĠĠĠ Ġ* Ġstep Ġ 2 ãĢģ Ġ åħĪ å¤ĦçĲĨ == ç®Ĺ å¼ı ï¼Į ä½¿ å¾Ĺ ä»ĸä»¬ éĢļè¿ĩ çĽ¸ çŃī åħ³ç³» åĲĦ èĩª åĭ ¾ ç»ĵ æĪĲ éĹ¨ æ´¾ ï¼Ľ ĊĠĠĠĠ Ġ* Ġstep Ġ 3 ãĢģ Ġ çĦ¶åĲİ å¤ĦçĲĨ != ç®Ĺ å¼ı ï¼Į æ£ĢæŁ¥ ä¸į çŃī åħ³ç³» æĺ¯åĲ¦ çł´ åĿ ı äºĨ çĽ¸ çŃī åħ³ç³» çļĦ è¿ŀ éĢļ æĢ§ ãĢĤ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġequations Possible ( equ ations : ĠArray < String >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġu f Ġ= ĠU F ( 2 6 ) ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( eq : ĠString Ġin Ġequations ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( eq [ 1 ] Ġ== Ġ'= ') Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġeq [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġeq [ 3 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġu f . union ( x Ġ- Ġ' a ', Ġy Ġ- Ġ' a ') ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( eq : ĠString Ġin Ġequations ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( eq [ 1 ] Ġ== Ġ' !') Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġeq [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġeq [ 3 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// åĪ¤æĸŃ æĺ¯åĲ¦ è¿ŀ éĢļ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( uf . connected ( x Ġ- Ġ' a ', Ġy Ġ- Ġ' a ')) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} Ċ }