\u4ece\u56fe\u4e2d\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\uff0c\u5f53\u6211Find(F)\u7684\u65f6\u5019\uff0c\u627e\u5230\u201cF\u201d\u540e\uff0c\u6211\u4eec\u5f00\u59cb\u4e00\u76f4\u56de\u6eaf\uff0c\u5728\u56de\u6eaf\u7684\u8fc7\u7a0b\u4e2d\u7ed9\uff0c\u628a\u8be5\u8282\u70b9\u7684\u7236\u4eb2\u6307\u5411\u6839\u8282\u70b9\u3002\u6700\u7ec8<\/p>\n\n\n\n
\u6211\u4eec\u4f1a\u5f62\u6210\u4e00\u4e2a\u538b\u7f29\u540e\u7684\u6811\uff0c\u5f53\u6211\u4eec\u518d\u6b21Find(F)\u7684\u65f6\u5019\uff0c\u53ea\u8981O(1)\u7684\u65f6\u95f4\u5c31\u53ef\u4ee5\u83b7\u53d6\uff0c\u8fd9\u91cc\u6709\u4e2a\u6ce8\u610f\u7684\u5730\u65b9\u5c31\u662fRank\uff0c\u5f53\u6211\u4eec\u5728\u8def<\/p>\n\n\n\n
\u5f84\u538b\u7f29\u65f6\uff0c\u6700\u540e\u6811\u7684\u9ad8\u5ea6\u53ef\u80fd\u4f1a\u964d\u4f4e\uff0c\u53ef\u80fd\u4f60\u4f1a\u610f\u8bc6\u5230\u539f\u5148\u7684Rank\u5c31\u9700\u8981\u4fee\u6539\u4e86\uff0c\u6240\u4ee5\u6211\u8981\u8bf4\u7684\u5c31\u662f\uff0c\u5f53\u8def\u5f84\u538b\u7f29\u65f6\uff0cRank\u4fdd\u5b58\u7684\u5c31<\/p>\n\n\n\n
\u662f\u6811\u9ad8\u5ea6\u7684\u4e0a\u754c\uff0c\u800c\u4e0d\u4ec5\u4ec5\u662f\u660e\u786e\u7684\u6811\u9ad8\u5ea6\uff0c\u53ef\u4ee5\u7406\u89e3\u6210”\u4f38\u7f29\u6905”\u4f38\u65f6\u5019\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n
\n
1 #region \u67e5\u627ex\u6240\u5c5e\u7684\u96c6\u5408\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u67e5\u627ex\u6240\u5c5e\u7684\u96c6\u5408\n 4 \/\/\/ <\/summary>\n 5 \/\/\/ <param name=\"x\"><\/param>\n 6 \/\/\/ <returns><\/returns>\n 7 public char Find(char x)\n 8 {\n 9 \/\/\u5982\u679c\u76f8\u7b49\uff0c\u5219\u8bf4\u660e\u5df2\u7ecf\u5230\u6839\u8282\u70b9\u4e86\uff0c\u8fd4\u56de\u6839\u8282\u70b9\u5143\u7d20\n10 if (dic[x].parent == x)\n11 return x;\n12 \n13 \/\/\u8def\u5f84\u538b\u7f29(\u56de\u6eaf\u7684\u65f6\u5019\u8d4b\u503c\uff0c\u6700\u7ec8\u7684\u503c\u5c31\u662f\u4e0a\u9762\u8fd4\u56de\u7684\"x\"\uff0c\u4e5f\u5c31\u662f\u4e00\u6761\u8def\u5f84\u4e0a\u5168\u90e8\u88ab\u4fee\u6539\u4e86)\n14 return dic[x].parent = Find(dic[x].parent);\n15 }\n16 #endregion<\/pre>\n<\/div>\n\n\n\n\u6211\u4eec\u6ce8\u610f\u5230\uff0c\u5728\u8def\u5f84\u538b\u7f29\u540e\uff0c\u6211\u4eec\u5c06LogN\u7684\u590d\u6742\u5ea6\u964d\u4f4e\u5230Alpha(N)\uff0cAlpha(N)\u53ef\u4ee5\u7406\u89e3\u6210\u4e00\u4e2a\u6bd4hash\u51fd\u6570\u8fd8\u6709\u5c0f\u7684\u5e38\u91cf\uff0c\u563f\u563f\uff0c\u8fd9<\/p>\n\n\n\n
\u5c31\u662f\u7b97\u6cd5\u7684\u9b45\u529b\u3002<\/p>\n\n\n\n
\u6700\u540e\u4e0a\u4e00\u4e0b\u603b\u7684\u8fd0\u884c\u4ee3\u7801\uff1a<\/p>\n\n\n\n
\n
\n
\n
\n\n\n\n1<\/div>\n 2<\/div>\n 3<\/div>\n 4<\/div>\n 5<\/div>\n 6<\/div>\n 7<\/div>\n 8<\/div>\n 9<\/div>\n 10<\/div>\n 11<\/div>\n 12<\/div>\n 13<\/div>\n 14<\/div>\n 15<\/div>\n 16<\/div>\n 17<\/div>\n 18<\/div>\n 19<\/div>\n 20<\/div>\n 21<\/div>\n 22<\/div>\n 23<\/div>\n 24<\/div>\n 25<\/div>\n 26<\/div>\n 27<\/div>\n 28<\/div>\n 29<\/div>\n 30<\/div>\n 31<\/div>\n 32<\/div>\n 33<\/div>\n 34<\/div>\n 35<\/div>\n 36<\/div>\n 37<\/div>\n 38<\/div>\n 39<\/div>\n 40<\/div>\n 41<\/div>\n 42<\/div>\n 43<\/div>\n 44<\/div>\n 45<\/div>\n 46<\/div>\n 47<\/div>\n 48<\/div>\n 49<\/div>\n 50<\/div>\n 51<\/div>\n 52<\/div>\n 53<\/div>\n 54<\/div>\n 55<\/div>\n 56<\/div>\n 57<\/div>\n 58<\/div>\n 59<\/div>\n 60<\/div>\n 61<\/div>\n 62<\/div>\n 63<\/div>\n 64<\/div>\n 65<\/div>\n 66<\/div>\n 67<\/div>\n 68<\/div>\n 69<\/div>\n 70<\/div>\n 71<\/div>\n 72<\/div>\n 73<\/div>\n 74<\/div>\n 75<\/div>\n 76<\/div>\n 77<\/div>\n 78<\/div>\n 79<\/div>\n 80<\/div>\n 81<\/div>\n 82<\/div>\n 83<\/div>\n 84<\/div>\n 85<\/div>\n 86<\/div>\n 87<\/div>\n 88<\/div>\n 89<\/div>\n 90<\/div>\n 91<\/div>\n 92<\/div>\n 93<\/div>\n 94<\/div>\n 95<\/div>\n 96<\/div>\n 97<\/div>\n 98<\/div>\n 99<\/div>\n 100<\/div>\n 101<\/div>\n 102<\/div>\n 103<\/div>\n 104<\/div>\n 105<\/div>\n 106<\/div>\n 107<\/div>\n 108<\/div>\n 109<\/div>\n 110<\/div>\n 111<\/div>\n 112<\/div>\n 113<\/div>\n 114<\/div>\n 115<\/div>\n 116<\/div>\n 117<\/div>\n 118<\/div>\n 119<\/div>\n 120<\/div>\n 121<\/div>\n 122<\/div>\n 123<\/div>\n 124<\/div>\n 125<\/div>\n 126<\/div>\n 127<\/div>\n 128<\/div>\n 129<\/div>\n 130<\/div>\n 131<\/div>\n 132<\/div>\n 133<\/div>\n 134<\/div>\n 135<\/div>\n 136<\/div>\n 137<\/div>\n 138<\/div>\n 139<\/div>\n 140<\/div>\n 141<\/div>\n 142<\/div>\n 143<\/div>\n<\/td>\n \n\n using<\/code> System;<\/code><\/div>\nusing<\/code> System.Collections.Generic;<\/code><\/div>\nusing<\/code> System.Linq;<\/code><\/div>\nusing<\/code> System.Text;<\/code><\/div>\n <\/div>\n namespace<\/code> ConsoleApplication1<\/code><\/div>\n{<\/code><\/div>\n <\/code>class<\/code> Program<\/code><\/div>\n <\/code>{<\/code><\/div>\n <\/code>static<\/code> void<\/code> Main(<\/code>string<\/code>[] args)<\/code><\/div>\n <\/code>{<\/code><\/div>\n <\/code>\/\/\u5b9a\u4e49 6 \u4e2a\u8282\u70b9<\/code><\/div>\n <\/code>char<\/code>[] c = <\/code>new<\/code> char<\/code>[] { <\/code>'A'<\/code>, <\/code>'B'<\/code>, <\/code>'C'<\/code>, <\/code>'D'<\/code>, <\/code>'E'<\/code>, <\/code>'F'<\/code> };<\/code><\/div>\n <\/div>\n <\/code>DisjointSet <\/code>set<\/code> = <\/code>new<\/code> DisjointSet();<\/code><\/div>\n <\/div>\n <\/code>set<\/code>.Init(c);<\/code><\/div>\n <\/div>\n <\/code>set<\/code>.Union(<\/code>'E'<\/code>, <\/code>'F'<\/code>);<\/code><\/div>\n <\/div>\n <\/code>set<\/code>.Union(<\/code>'C'<\/code>, <\/code>'D'<\/code>
| |
![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/04\/fuck.gif\")
<\/a><\/figure>\n\n\n\n