2493. گره ها را به حداکثر تعداد گروه تقسیم کنید

2493. گره ها را به حداکثر تعداد گروه تقسیم کنید

مشکل: سخت

مباحث: Breadth-First Searchبا Union Findبا Graph

به شما یک عدد صحیح مثبت داده می شود n تعداد گره ها در محرک نمودار گره ها از 1 به nبشر

همچنین به شما یک آرایه عدد صحیح 2D داده می شود edges، کجا edges[i] = [ai, bi] نشان می دهد که وجود دارد دو طرفه لبه بین گره ها ai وت biبشر اخطار که نمودار داده شده ممکن است قطع شود.

گره های نمودار را به m گروه ها (1-شاخص) به گونه ای که:

• هر گره در نمودار دقیقاً به یک گروه تعلق دارد.
• برای هر جفت گره در نمودار که توسط یک لبه وصل شده اند [ai, bi]، اگر ai متعلق به گروه با فهرست است xوت bi متعلق به گروه با فهرست است y، پس |y - x| = 1بشر

بازگشت حداکثر تعداد گروه ها (یعنی حداکثر m) که می توانید گره ها را تقسیم کنیدبشر بازگشت -1 اگر گروه بندی گره ها با شرایط خاص غیرممکن استبشر

مثال 1:

• ورودی: n = 6 ، لبه ها = [[1,2]با[1,4]با[1,5]با[2,6]با[2,3]با[4,6]]
• خروجی: 4
• توضیح: همانطور که در تصویر نشان داده شده است:
  • گره 5 را به گروه اول اضافه کنید.
  • گره 1 را به گروه دوم اضافه کنید.
  • گره های 2 و 4 را به گروه سوم اضافه کنید.
  • گره های 3 و 6 را به گروه چهارم اضافه کنید.
  • می بینیم که هر لبه راضی است.
  • می توان نشان داد که اگر یک گروه پنجم ایجاد کنیم و هر گره را از گروه سوم یا چهارم به آن منتقل کنیم ، حداقل در لبه ها راضی نخواهد شد.

مثال 2:

• ورودی: n = 3 ، لبه ها = [[1,2]با[2,3]با[3,1]]
• خروجی: -1
• توضیح: اگر گره 1 را به گروه اول ، گره 2 به گروه دوم و گره 3 به گروه سوم اضافه کنیم تا دو لبه اول را برآورده کنیم ، می بینیم که لبه سوم راضی نخواهد شد.
  • می توان نشان داد که هیچ گروه بندی امکان پذیر نیست.

محدودیت ها:

• 1 <= n <= 500
• 1 <= edges.length <= 104
• edges[i].length == 2
• 1 <= ai, bi <= n
• ai != bi
• حداکثر یک لبه بین هر جفت رئوس وجود دارد.

نکته:

1. اگر نمودار دو طرفه نباشد ، گروه بندی گره ها امکان پذیر نیست.
2. توجه کنید که ما می توانیم مشکل را برای هر یک از مؤلفه های متصل به طور مستقل حل کنیم و پاسخ نهایی فقط مجموع حداکثر تعداد گروه در هر مؤلفه خواهد بود.
3. سرانجام ، برای حل مشکل برای هر یک از مؤلفه های متصل ، می توانیم متوجه شویم که اگر برای برخی از گره های V موقعیت خود را در سمت چپ ترین گروه قرار دهیم ، می توانیم موقعیت هر گره دیگر را نیز ارزیابی کنیم. این موقعیت عمق گره در یک درخت BFS پس از ریشه کن کردن در گره V است.

راه حل:

مشکل ، “گره ها را به حداکثر تعداد گروه تقسیم کنید”، شامل تعیین حداکثر تعداد گروه هایی است که گره های یک نمودار غیر مستقیم در آن می توانند تقسیم شوند ، به گونه ای که:

1. هر گره دقیقاً به یک گروه تعلق دارد.
2. گره های مجاور در گروه هایی هستند که شاخص های آنها دقیقاً با 1 متفاوت است. اگر نمودار دو طرفه نباشد ، گروه بندی غیرممکن است و عملکرد باید برگردد -1بشر

نکات کلیدی

• خصوصیات نمودار: نمودار ممکن است قطع شود.
• اعتبار سنجی: برای هر مؤلفه متصل ، بررسی کنید که آیا این دو طرفه است. اگر نه ، برگردید -1بشر
• طبیعت دو طرفه: راه حل شامل BFS برای اعتبارسنجی دو حزب است.
• اتحادیه- برای گروه بندی مؤلفه های متصل به طور کارآمد مفید است.

رویکرد

1. پیش پردازش:

   • نمودار را با استفاده از یک لیست مجاور نشان دهید.
   • برای شناسایی اجزای متصل از اتحادیه استفاده کنید.

2. BFS برای اعتبار سنجی دو طرفه:

   • برای هر مؤلفه متصل ، از BFS استفاده کنید تا مشخص شود که آیا این دو طرفه است.
   • اگر دو طرفه نیست ، برگردید -1بشر

3. تعداد گروه را محاسبه کنید:

   • برای هر مؤلفه متصل ، از BFS برای تعیین حداکثر عمق استفاده کنید ، که حداکثر تعداد گروه ها را نشان می دهد.

4. ترکیب نتایج:

   • تعداد حداکثر تعداد گروه از تمام اجزای دو حزب را جمع کنید.

برنامه ریزی کردن

1. نمودار را به عنوان یک لیست مجاور بسازید.
2. از اجزای متصل به گروه استفاده کنید.
3. برای هر گره در نمودار:
   • برای بررسی اینکه آیا نمودار دو طرفه است و حداکثر عمق آن مؤلفه را محاسبه کنید ، از BFS استفاده کنید.
4. به عنوان نتیجه ، مبلغ اعماق همه مؤلفه ها را برگردانید. اگر هر مؤلفه دو طرفه نیست ، برگردید -1بشر

بیایید این راه حل را در PHP پیاده سازی کنیم: 2493. گره ها را به حداکثر تعداد گروه تقسیم کنید

/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function magnificentSets($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $graph
 * @param $u
 * @return int
 */
private function bfs($graph, $u) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

class UnionFind {
    /**
     * @var array
     */
    private $id;
    /**
     * @var array
     */
    private $rank;

    /**
     * @param $n
     */
    public function __construct($n) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $u
     * @param $v
     * @return void
     */
    public function unionByRank($u, $v) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $u
     * @return mixed
     */
    public function find($u) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}


// Example usage:
$n = 6;
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
echo maxGroups($n, $edges); // Output: 4

$n = 3;
$edges = [[1,2], [2,3], [3,1]];
echo maxGroups($n, $edges); // Output: -1
?>

توضیح:

1. کلاس اتحادیه

ساختار ساختار اتحادیه (Unjoint Set Set Union) گره ها را به اجزای متصل تبدیل کرده و دو کار اصلی را انجام می دهد:

• پیدا کردن: ریشه مؤلفه متصل یک گره را مشخص کنید.
• اتحادیه: دو مؤلفه متصل را بر اساس رتبه ادغام کنید.

2. BFS برای بررسی دو طرفه و محاسبه عمق

• اعتبار سنجی دو طرفه: با استفاده از BFS ، “رنگ” متناوب را به گره ها اختصاص دهید. اگر گره های مجاور همان رنگ را به اشتراک بگذارند ، نمودار دو طرفه نیست.
• محاسبه عمق: برای تعیین حداکثر تعداد گروه ها ، عمق درخت BFS را اندازه گیری کنید.

3. نتایج را ترکیب کنید

• حداکثر عمق را برای هر مؤلفه متصل محاسبه کنید.
• برای تعیین نتیجه ، عمق را برای همه مؤلفه ها اضافه کنید.

به عنوان مثال پیاده روی

مثال 1

ورودی:

$n = 6;  
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];

مراحل:

1. ساخت لیست مجاورت:

   1 -> [2, 4, 5]
   2 -> [1, 3, 6]
   3 -> [2]
   4 -> [1, 6]
   5 -> [1]
   6 -> [2, 4]

1. از BFS روی اجزای متصل استفاده کنید:
   • مؤلفه 1: دو طرفه. حداکثر عمق = 4.
2. عمق جمع در تمام مؤلفه ها: 4بشر

خروجی: 4

مثال 2

ورودی:

$n = 3;  
$edges = [[1,2], [2,3], [3,1]];

مراحل:

1. ساخت لیست مجاورت:

   1 -> [2, 3]
   2 -> [1, 3]
   3 -> [1, 2]

1. از BFS استفاده کنید:
   • مؤلفه 1: دو طرفه نیست.

خروجی: -1

پیچیدگی زمانی

• ساخت نمودار: o (ه)، کجا اشمیه تعداد لبه ها است.
• اتحادیه- o (a (n))، کجا حرف تعداد گره ها (تقریباً ثابت به دلیل فشرده سازی مسیر) است.
• BFS: O (V + E)، کجا حرفهای تعداد راس ها است. پیچیدگی کلی: o (n + e)

خروجی برای مثال

$n = 6;
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
echo magnificentSets($n, $edges); // Output: 4

$n = 3;
$edges = [[1,2], [2,3], [3,1]];
echo magnificentSets($n, $edges); // Output: -1

این رویکرد با استفاده از BFS برای بررسی های دو طرفه و محاسبات عمق در هنگام استفاده از اتحادیه برای ساده سازی مدیریت مؤلفه ، مشکل گروه بندی را به کار می برد. محلول هر دو نمودار متصل و جدا شده را کنترل می کند.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: