گراف همیلتون در کوئرا(آزمون 42)
دو سال پیش منتشر شده
تعداد بازدید: 214
کد پروژه: 363853
شرح پروژه
گراف همیلتونی
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
فرض کنید GG یک گراف ساده nn راسی mm یالی است که راس‌های آن از 11 تا nn شماره گذاری شده است.
به یک گراف هملیتونی می‌گوییم اگر دوری داشته باشد که از هر راس دقیقا یکبار عبور کند.
یک گراف به شما داده می‌شود که همیلتونی است، از شما می‌خواهیم یکی از دورهای همیلتونی آن را پیدا کنید.
ورودی
در سطر اول ورودی دو عدد صحیح nn و mm که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف GG است.
3≤n≤1003≤n≤100 n≤m≤n(n−1)2n≤m≤2
n(n−1)
در mm سطر بعدی دو عدد uiui و vivi که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال uiviuivi در گراف GG است.
1≤ui≠vi≤n1≤ui≠vi≤n
تضمین می‌شود گراف داده شده ساده است. یعنی بین هر دو راس حداکثر یک یال آمده است.
خروجی
در تنها سطر خروجی یکی از جایگشت‌های اعداد 11 تا nn مثل v1,v2,…,vnv1,v2,…,vn را چاپ کنید به طوری که تشکیل یک دور همیلتونی بدهد؛ یعنی vivi و vi%n+1vi%n+1 برای هر ii از 11 تا nn به یکدیگر یال داشته باشند.
مهارت ها و تخصص های مورد نیاز
مهلت برای انجام
4روز
وضعیت مناقصه
بسته
درباره کارفرما
عضویت دو سال پیش
