در این مطلب، ویدئو اتصال اضافی – پیدا کردن اتحادیه – Leetcode 684 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:16:03
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:01,680
سلام به همه خوش آمدید و بیایید امروز
2
00:00:01,680 –> 00:00:03,600
چند کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:03,600 –> 00:00:05,440
بیایید اتصالات اضافی را حل کنیم، اما
4
00:00:05,440 –> 00:00:07,120
قبل از انجام این کار، فقط می خواهم به
5
00:00:07,120 –> 00:00:08,880
شما بگویم اگر مشکلی دارید،
6
00:00:08,880 –> 00:00:10,400
می توانید آنها را در نظرات بگذارید
7
00:00:10,400 –> 00:00:11,360
.
8
00:00:11,360 –> 00:00:13,120
که من
9
00:00:13,120 –> 00:00:14,480
در حال حاضر در حال انجام آن هستم، بنابراین ممکن است
10
00:00:14,480 –> 00:00:16,079
چند هفته طول بکشد تا به مشکل پیشنهادی شما برسم،
11
00:00:16,079 –> 00:00:18,800
بنابراین این یک مشکل بسیار خوب
12
00:00:18,800 –> 00:00:19,359
برای حل
13
00:00:19,359 –> 00:00:21,199
آن است که در واقع می توان آن را به روشی ساده لوحانه
14
00:00:21,199 –> 00:00:23,119
حل کرد که o از n مربع خواهد بود
15
00:00:23,119 –> 00:00:24,800
و این فقط یک راه حل اولیه مانند عمق
16
00:00:24,800 –> 00:00:26,880
جستجوی اولیه برای آن برای این نمودار است که
17
00:00:26,880 –> 00:00:28,720
مشابه بسیاری از مشکلات نمودار دیگر است، اما
18
00:00:28,720 –> 00:00:30,320
در واقع می توانید این را
19
00:00:30,320 –> 00:00:33,920
به یک o معمولی از n یک راه حل بهینه تر کاهش دهید
20
00:00:33,920 –> 00:00:35,920
و در واقع به الگوریتمی نیاز دارد
21
00:00:35,920 –> 00:00:37,520
که ممکن است
22
00:00:37,520 –> 00:00:37,920
قبل از
23
00:00:37,920 –> 00:00:40,480
پیدا کردن اتحاد ندیده باشید. این یک الگوریتم نادر است که
24
00:00:40,480 –> 00:00:42,800
در کد نشت نیاز دارد، بنابراین اکثر مردم از آن استفاده نمیکنند،
25
00:00:42,800 –> 00:00:45,840
اما این مشکل میتواند از union find برای
26
00:00:45,840 –> 00:00:47,520
دستیابی به راهحل بسیار بهتر استفاده کند،
27
00:00:47,520 –> 00:00:49,360
من همچنین توضیح خواهم داد که چرا ما
28
00:00:49,360 –> 00:00:51,360
مجاز به استفاده از union fi هستیم. الگوریتم
29
00:00:51,360 –> 00:00:53,120
nd در این مسئله چون خیلی
30
00:00:53,120 –> 00:00:53,760
واضح نیست،
31
00:00:53,760 –> 00:00:56,399
بنابراین تعریفی به ما داده می شود که درخت یک
32
00:00:56,399 –> 00:00:57,600
گراف بدون جهت است
33
00:00:57,600 –> 00:01:00,399
که هیچ چرخه ای ندارد، بنابراین اساساً
34
00:01:00,399 –> 00:01:02,239
این کلید یک گراف غیر جهت دار است که
35
00:01:02,239 –> 00:01:03,520
شامل هیچ چرخه ای نیست، به
36
00:01:03,520 –> 00:01:05,760
ما گرافی داده می شود که به عنوان یک
37
00:01:05,760 –> 00:01:07,520
درخت بهعنوان یک
38
00:01:07,520 –> 00:01:08,240
گراف بدون جهت شروع شد
39
00:01:08,240 –> 00:01:11,040
و چرخهای نداشت، ما n گره داشتیم این
40
00:01:11,040 –> 00:01:12,159
گرهها از
41
00:01:12,159 –> 00:01:15,040
یک تا n برچسبگذاری شدهاند، اما در نهایت
42
00:01:15,040 –> 00:01:15,600
43
00:01:15,600 –> 00:01:18,159
یک یال اضافی اضافه کردیم و میدانیم که هر
44
00:01:18,159 –> 00:01:19,840
یال اساساً فقط
45
00:01:19,840 –> 00:01:22,159
دو راس را به هم متصل میکند و این یال بدون جهت است.
46
00:01:22,159 –> 00:01:23,280
بنابراین این
47
00:01:23,280 –> 00:01:25,200
یال به اتصال دو راس ختم می شود
48
00:01:25,200 –> 00:01:27,040
و این یال
49
00:01:27,040 –> 00:01:29,920
قبلاً در نمودار وجود نداشته است، در
50
00:01:29,920 –> 00:01:31,119
این حالت
51
00:01:31,119 –> 00:01:33,520
نمودار به صورت آرایه ای از یال ها نشان داده می شود
52
00:01:33,520 –> 00:01:35,280
و تعداد یال ها اساساً
53
00:01:35,280 –> 00:01:37,520
n است و اساساً تعداد یال ها برابر
54
00:01:37,520 –> 00:01:40,000
با عدد است. از گره هایی که داریم
55
00:01:40,000 –> 00:01:41,680
همانطور که اشاره کردم هر یال قرار است
56
00:01:41,680 –> 00:01:43,840
دو گره را به هم وصل کند،
57
00:01:43,840 –> 00:01:46,159
بنابراین می خواهیم یک یال را برگردانیم که بتوان آن
58
00:01:46,159 –> 00:01:48,000
را از نمودار حذف
59
00:01:48,000 –> 00:01:50,640
کرد که گراف را دوباره به
60
00:01:50,640 –> 00:01:51,439
درخت تبدیل می کند
61
00:01:51,439 –> 00:01:53,680
اگر یالهای متعددی هستند که میتوانیم آنها را
62
00:01:53,680 –> 00:01:55,840
حذف کنیم که گراف را دوباره
63
00:01:55,840 –> 00:01:57,040
به یک درخت تبدیل میکند،
64
00:01:57,040 –> 00:02:00,399
سپس آخرین یال
65
00:02:00,399 –> 00:02:03,040
ورودی را که اساساً آن شرط را برآورده میکند، برمیگردانیم
66
00:02:03,040 –> 00:02:03,840
67
00:02:03,840 –> 00:02:06,719
و آنها به ما تضمین میکنند که در
68
00:02:06,719 –> 00:02:08,399
لیست ورودی یالهایی که
69
00:02:08,399 –> 00:02:11,280
هر یال داده شده است. منحصر به فرد خواهد بود،
70
00:02:11,280 –> 00:02:12,879
بنابراین بیایید به این مثال نگاهی بیندازیم،
71
00:02:12,879 –> 00:02:16,000
توجه کنید که اگر هر یک
72
00:02:16,000 –> 00:02:17,680
از یال ها را حذف کنیم،
73
00:02:17,680 –> 00:02:19,920
اکنون این نمودار دیگر چرخه
74
00:02:19,920 –> 00:02:20,959
درستی ندارد زیرا
75
00:02:20,959 –> 00:02:23,200
در ابتدا این چرخه درست بود، بنابراین اگر این یال را حذف کنم، این چرخه درست است.
76
00:02:23,200 –> 00:02:24,080
77
00:02:24,080 –> 00:02:26,000
چرخهای ندارم که
78
00:02:26,000 –> 00:02:27,599
شرط را برآورده کند، به این
79
00:02:27,599 –> 00:02:28,000
معنی است که
80
00:02:28,000 –> 00:02:30,800
یک دو نتیجه است یک دو
81
00:02:30,800 –> 00:02:32,160
یال است که میتوانیم
82
00:02:32,160 –> 00:02:34,879
نه را برگردانیم زیرا معلوم میشود که اگر این
83
00:02:34,879 –> 00:02:35,440
یال
84
00:02:35,440 –> 00:02:37,360
را حذف کنم، شرایط را نیز برآورده میکند
85
00:02:37,360 –> 00:02:39,519
، چرخهای که در ابتدا داشتیم را میشکند. در مورد
86
00:02:39,519 –> 00:02:41,920
یال سوم هم همینطور است، بنابراین
87
00:02:41,920 –> 00:02:42,879
در این مورد،
88
00:02:42,879 –> 00:02:44,800
کدام یک از این سه
89
00:02:44,800 –> 00:02:46,239
یال را میخواهیم برگردانیم، اساساً کدام یال
90
00:02:46,239 –> 00:02:47,360
91
00:02:47,360 –> 00:02:50,080
در ورودی که 2 3 خواهد بود
92
00:02:50,080 –> 00:02:50,720
93
00:02:50,720 –> 00:02:52,400
را برگردانیم. یو
94
00:02:52,400 –> 00:02:54,480
ممکن است همیشه
95
00:02:54,480 –> 00:02:55,840
اینطور باشد، اگر
96
00:02:55,840 –> 00:02:57,840
هر یک از لبه ها را برداریم، چرخه را می شکند، به طوری
97
00:02:57,840 –> 00:02:59,680
که آیا همیشه
98
00:02:59,680 –> 00:03:01,920
هر چه آخرین لبه به ما داده می
99
00:03:01,920 –> 00:03:03,760
شود، برمی گردانیم، نه لزوماً اجازه دهید به دیگری نگاهی بیندازیم.
100
00:03:03,760 –> 00:03:05,920
یال اگر اضافه کردیم، فرض می کنیم دو
101
00:03:05,920 –> 00:03:08,080
چهار در اصل اگر
102
00:03:08,080 –> 00:03:09,280
تعداد گره ها را
103
00:03:09,280 –> 00:03:11,599
از سه به چهار افزایش دادم، بنابراین یک یال
104
00:03:11,599 –> 00:03:12,400
در اینجا اضافه کردم
105
00:03:12,400 –> 00:03:15,519
که این دو گره را اکنون در
106
00:03:15,519 –> 00:03:18,080
صورت شکستن به هم وصل می کند و این آخرین لبه است که
107
00:03:18,080 –> 00:03:20,080
در ورودی ما در صورت شکستن رخ می دهد.
108
00:03:20,080 –> 00:03:22,400
این لبه باعث خلاص شدن از شر حلقه
109
00:03:22,400 –> 00:03:24,239
ای می شود که ما نداریم، ما هنوز یک حلقه
110
00:03:24,239 –> 00:03:25,519
در اینجا داریم، بنابراین
111
00:03:25,519 –> 00:03:28,080
شکستن این لبه ما
112
00:03:28,080 –> 00:03:29,680
را به درختی تبدیل نمی کند که همان چیزی است که ما به دنبال
113
00:03:29,680 –> 00:03:30,000
114
00:03:30,000 –> 00:03:31,280
آن بودیم، بنابراین همیشه قرار نیست آن را
115
00:03:31,280 –> 00:03:33,920
برگردانیم. آخرین لبه سوال بعدی من
116
00:03:33,920 –> 00:03:34,640
از شما این است
117
00:03:34,640 –> 00:03:37,519
که اگر n گره داریم و n یال داریم
118
00:03:37,519 –> 00:03:39,120
درست این چیزی است که به ما داده می شود همیشه به
119
00:03:39,120 –> 00:03:40,480
ما همیشه همان تعداد
120
00:03:40,480 –> 00:03:41,760
گره به همان تعداد یال داده می
121
00:03:41,760 –> 00:03:44,239
شود آیا تضمین می شود که همیشه
122
00:03:44,239 –> 00:03:46,720
به با یک حلقه شروع کنید و پاسخ
123
00:03:46,720 –> 00:03:47,040
این است که
124
00:03:47,040 –> 00:03:49,519
بله اجازه دهید به شما شهودی را نشان می دهد که چرا
125
00:03:49,519 –> 00:03:50,400
این درست است
126
00:03:50,400 –> 00:03:53,280
، فرض کنید ما با دو گره شروع می کنیم، اگر
127
00:03:53,280 –> 00:03:54,159
128
00:03:54,159 –> 00:03:57,120
یک لبه به این اعلان اضافه کنم چگونه توانستیم
129
00:03:57,120 –> 00:03:58,000
130
00:03:58,000 –> 00:04:01,120
تعداد کل نمودارهای غیرمتناسب را بگیریم
131
00:04:01,120 –> 00:04:03,360
، ما دو نمودار داشتیم که به محض اضافه کردن یک گراف درست به هم متصل نبودند.
132
00:04:03,360 –> 00:04:03,920
133
00:04:03,920 –> 00:04:06,400
edge ما توانستیم
134
00:04:06,400 –> 00:04:07,920
آن عدد را
135
00:04:07,920 –> 00:04:10,159
به یک نمودار کاهش دهیم در حال حاضر یک
136
00:04:10,159 –> 00:04:11,599
گراف متصل داریم
137
00:04:11,599 –> 00:04:13,439
و میخواهید چیزی در مورد یک
138
00:04:13,439 –> 00:04:14,640
گراف متصل
139
00:04:14,640 –> 00:04:17,759
بدانید اگر یک یال جدید به این نمودار متصل اضافه
140
00:04:17,759 –> 00:04:18,238
141
00:04:18,238 –> 00:04:20,798
کنید، میخواهید یک چرخه ایجاد کنید، برای
142
00:04:20,798 –> 00:04:21,759
مثال در این در صورتی
143
00:04:21,759 –> 00:04:23,919
که حتی
144
00:04:23,919 –> 00:04:25,840
لبههای ممکن منحصربهفردتری نداریم، میتوانیم به غیر از
145
00:04:25,840 –> 00:04:26,720
مثلاً یک
146
00:04:26,720 –> 00:04:29,520
حلقه خود روی دو یا یک حلقه خود روی یکی
147
00:04:29,520 –> 00:04:30,560
یا فقط اضافه کردن
148
00:04:30,560 –> 00:04:32,400
یک یال دیگر به سمت راست، اضافه کنیم، اما میدانیم که
149
00:04:32,400 –> 00:04:34,080
یالها اساساً چیزی که من میگویم بدون جهت هستند.
150
00:04:34,080 –> 00:04:34,800
این است که
151
00:04:34,800 –> 00:04:37,520
اگر ما به اضافه کردن یالهایی به نموداری
152
00:04:37,520 –> 00:04:39,759
که قبلاً یک گراف متصل است،
153
00:04:39,759 –> 00:04:41,600
ادامه دهیم، یک چرخه ایجاد میکنیم، بیایید به
154
00:04:41,600 –> 00:04:43,280
چند مثال دیگر نگاه کنیم،
155
00:04:43,280 –> 00:04:46,720
بنابراین اگر چهار
156
00:04:46,720 –> 00:04:49,120
یال به این نمودار اضافه کنم، اگر چهار یال را به این نمودار اضافه کنم، اکنون چهار گره
157
00:04:49,120 –> 00:04:51,520
داریم. به پایان می رسد با یک چرخه
158
00:04:51,520 –> 00:04:52,880
، غیرممکن است که
159
00:04:52,880 –> 00:04:55,440
اگر چهار
160
00:04:55,440 –> 00:04:57,520
یال منحصر به فرد را به این نمودار اضافه کنیم، به یک چرخه ختم نشویم، اجازه دهید به
161
00:04:57,520 –> 00:04:58,320
شما نشان دهم که
162
00:04:58,320 –> 00:05:01,120
چرا فرض کنید یک یال را در اینجا اضافه کرده ایم، سپس
163
00:05:01,120 –> 00:05:01,759
می توانیم
164
00:05:01,759 –> 00:05:03,919
یک یال دیگر را در اینجا اضافه کنیم و سپس
165
00:05:03,919 –> 00:05:05,520
می توانیم یال دیگری را
166
00:05:05,520 –> 00:05:07,520
در اینجا اضافه کنیم. سپس لبه چهارمی که میتوانیم
167
00:05:07,520 –> 00:05:08,639
اضافه کنیم، اینجاست که به
168
00:05:08,639 –> 00:05:10,560
این ترتیب به یک چرخه میرسیم، اما دست نگه دارید،
169
00:05:10,560 –> 00:05:12,240
شاید احتمالات دیگری وجود داشته
170
00:05:12,240 –> 00:05:12,639
171
00:05:12,639 –> 00:05:15,759
باشد، شاید به جای اتصال اینها، من
172
00:05:15,759 –> 00:05:17,039
همچنین
173
00:05:17,039 –> 00:05:19,199
میتوانم اینها را وصل کنم که به چرخه خیلی
174
00:05:19,199 –> 00:05:20,479
درست ختم میشود، توجه کنید که
175
00:05:20,479 –> 00:05:22,720
شاید ما فقط این را با
176
00:05:22,720 –> 00:05:24,320
هیچ چیز دیگری وصل نمی کنیم، شاید یک یال در اینجا اضافه کنیم
177
00:05:24,320 –> 00:05:25,919
که به چرخه ختم می شود،
178
00:05:25,919 –> 00:05:27,919
اگر من یک یال را در اینجا اضافه کنم که
179
00:05:27,919 –> 00:05:30,080
به یک چرخه ختم می شود مهم نیست چگونه آن را انجام دهیم، در
180
00:05:30,080 –> 00:05:31,680
نهایت به یک
181
00:05:31,680 –> 00:05:33,680
چرخه می رسیم. اینگونه شروع کنم، من سعی
182
00:05:33,680 –> 00:05:35,600
می کنم اکنون باهوش باشم که هنوز چه چیزی
183
00:05:35,600 –> 00:05:37,199
را با یک چرخه به پایان می رسانیم و
184
00:05:37,199 –> 00:05:39,280
این درست خواهد بود، مهم نیست
185
00:05:39,280 –> 00:05:39,919
که اگر
186
00:05:39,919 –> 00:05:42,560
n گره و n یال منحصر به فرد داشته باشیم، بدون توجه به اینکه چه اتفاقی می افتد،
187
00:05:42,560 –> 00:05:43,840
به یک چرخه می رسیم.
188
00:05:43,840 –> 00:05:46,479
اما سوال من از شما این است
189
00:05:46,479 –> 00:05:47,120
که چگونه می
190
00:05:47,120 –> 00:05:49,199
دانید که الف درست کردن این یال،
191
00:05:49,199 –> 00:05:50,960
فرض کنید ما از قبل این سه یال را داریم،
192
00:05:50,960 –> 00:05:52,000
چگونه میدانید که
193
00:05:52,000 –> 00:05:54,639
افزودن این یال یک چرخه برای ما ایجاد میکند، به
194
00:05:54,639 –> 00:05:56,240
این دلیل که
195
00:05:56,240 –> 00:05:59,600
یکی از قبل با سه
196
00:05:59,600 –> 00:06:02,639
سه و یکی از قبل متصل شده است، ببینید
197
00:06:02,639 –> 00:06:03,039
چگونه
198
00:06:03,039 –> 00:06:06,319
هر چهار گره قبلاً
199
00:06:06,319 –> 00:06:07,199
متصل شدهاند.
200
00:06:07,199 –> 00:06:10,560
بنابراین وقتی این یال را اضافه
201
00:06:10,560 –> 00:06:11,680
میکنم، از قبل میدانستم که مسیری از
202
00:06:11,680 –> 00:06:14,560
سه برای رسیدن به یک وجود دارد، اکنون یک
203
00:06:14,560 –> 00:06:15,440
مسیر دوم
204
00:06:15,440 –> 00:06:17,840
از سه ایجاد میکنم تا به یک اطلاعیه برسم
205
00:06:17,840 –> 00:06:20,400
که چگونه این چیزی است که چرخه را ایجاد میکند،
206
00:06:20,400 –> 00:06:22,880
این دلیلی است که ما اجازه داریم
207
00:06:22,880 –> 00:06:25,199
از الگوریتم union find استفاده کنید
208
00:06:25,199 –> 00:06:27,120
زیرا ما به نمودارهای متصل نگاه می کنیم
209
00:06:27,120 –> 00:06:29,199
و هنگامی که آن را
210
00:06:29,199 –> 00:06:32,000
اضافه می کنیم یک بار متوجه شدیم که یک لبه
211
00:06:32,000 –> 00:06:33,039
در آرایه ورودی خود پیدا کرده ایم
212
00:06:33,039 –> 00:06:35,440
که باعث می شود یک نمودار متصل را بگیریم
213
00:06:35,440 –> 00:06:36,080
و
214
00:06:36,080 –> 00:06:39,039
یک اتصال اضافی اضافه کنیم به همین دلیل به این اتصالات اضافی می گویند.
215
00:06:39,039 –> 00:06:40,800
ما
216
00:06:40,800 –> 00:06:42,560
یک اتصال دیگر را اضافه کردیم که
217
00:06:42,560 –> 00:06:43,199
نیازی به
218
00:06:43,199 –> 00:06:45,360
سه مورد نبود، قبلاً میتوانستیم به یکی برسیم که چرا
219
00:06:45,360 –> 00:06:46,800
زحمت اضافه کردن این یال
220
00:06:46,800 –> 00:06:49,840
که یک حلقه ایجاد میکند و آخرین یال
221
00:06:49,840 –> 00:06:52,800
بهطوریکه اولین یال در لبههای آرایه ورودی
222
00:06:52,800 –> 00:06:53,360
223
00:06:53,360 –> 00:06:55,680
ما باعث قرمزی میشود را اضافه کنیم. اتصال نامطلوب
224
00:06:55,680 –> 00:06:57,759
لبهای خواهد بود که ما برمیگردانیم،
225
00:06:57,759 –> 00:06:59,280
بنابراین راهحلی که میخواهیم انجام دهیم این
226
00:06:59,280 –> 00:07:01,039
است که اتحاد پیدا کنیم و
227
00:07:01,039 –> 00:07:02,240
میخواهیم اتحاد یافتن را براساس رتبه انجام دهیم
228
00:07:02,240 –> 00:07:04,080
که کارآمدترین راه برای
229
00:07:04,080 –> 00:07:05,919
انجام آن است، بنابراین آنچه میخواهیم انجام دهیم. برای انجام این کار
230
00:07:05,919 –> 00:07:08,400
، تکرار از طریق هر یال است،
231
00:07:08,400 –> 00:07:09,360
به عنوان مثال
232
00:07:09,360 –> 00:07:11,440
این یک و دو، ما می دانیم که ما
233
00:07:11,440 –> 00:07:13,680
با سه گره درست شروع می کنیم،
234
00:07:13,680 –> 00:07:15,599
زیرا سه یال به ما داده می شود، بنابراین n برابر با
235
00:07:15,599 –> 00:07:17,360
سه، ما سه گره داریم که هر گره
236
00:07:17,360 –> 00:07:18,319
از یک
237
00:07:18,319 –> 00:07:20,560
دو تا سه سمت راست شماره گذاری می شود. بنابراین ما کار را با
238
00:07:20,560 –> 00:07:23,199
سه گره شروع می کنیم که به درستی به یکدیگر متصل نیستند
239
00:07:23,199 –> 00:07:24,400
240
00:07:24,400 –> 00:07:27,039
و رتبه هر یک از آن
241
00:07:27,039 –> 00:07:29,520
نمودارهای جداگانه یک است که اساساً به اندازه
242
00:07:29,520 –> 00:07:30,400
گراف است درست
243
00:07:30,400 –> 00:07:31,919
کاری که ما انجام می دهیم
244
00:07:31,919 –> 00:07:34,240
عبور از هر یال است، به عنوان مثال یک
245
00:07:34,240 –> 00:07:35,759
دو این بدان معناست که ما
246
00:07:35,759 –> 00:07:37,840
یک و دو را به
247
00:07:37,840 –> 00:07:40,080
یکدیگر وصل می کنیم، آنها را به شکل یک درخت به هم وصل می کنیم،
248
00:07:40,080 –> 00:07:42,240
بنابراین یکی از آنها
249
00:07:42,240 –> 00:07:44,080
گره والد
250
00:07:44,080 –> 00:07:45,759
دیگری خواهد بود و ما این کار را
251
00:07:45,759 –> 00:07:47,680
بر اساس رتبه انجام خواهیم داد. به عنوان مثال
252
00:07:47,680 –> 00:07:50,800
اگر اندازه این gra ph بود
253
00:07:50,800 –> 00:07:52,479
یا شاید ما چیز جداگانه ای
254
00:07:52,479