المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:برنامه نویسی:سوال ۷

سوال ۸

در این سوال شما بایستی برنامه‌ای بنویسید که مشخصات یک گراف ‎‎ بی‌جهت نه لزوماً ساده (یعنی ممکن است بین برخی از رئوس بیش از یک یال باشد و یا ممکن است یک راس به خودش چندین یال داشته باشد) را از ورودی استاندارد بخواند.‎

ورودی

در سطر اوّل فایل ورودی به ترتیب ‎$n$‎ و ‎$e$‎ تعداد راس‌ها و یال‌های گراف نوشته شده است. در ‎$e$‎ سطر بعدی در هر سطر دو عدد ‎$x$‎ و ‎$y$‎ نوشته شده که دو سر یکی از یال‌های گراف را مشخص می‌کند.

خروجی

فایل خروجی استاندارد بایستی ‎$n$‎ سطر داشته باشد که در سطر ‎$i$‎ ام همسایه‌های راس ‎$i$‎ نوشته شده‌اند. به ازای هر همسایه ‎$x$‎ (دقت کنید ‎$x$‎ می‌تواند مساوی ‎$i$‎‎ باشد) از راس ‎$i$‎ شما بایستی ابتدا ‎$x$‎ و سپس تعداد یال‌هایی که بین ‎$i$‎ و ‎$x$‎ وجود دارد را بنویسید. ‎

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2 4
1 1
1 2
1 1
2 1
2 2 1 2
1 2

‎ برنامه‌ی شما بایستی از ‎${\cal O}(e\times \log{n})$‎ باشد. ‎


ابزار صفحه