Salam ...
Angeh A2
" DAGy is made up of a directed acyclic graph plus one additional directed edge. With this additional edge a cycle forms that goes through every vertex in the graph. "
" DAGy can be put back in order if you find the maximal cycle that goes through every vertex. "
4 5
0 1
1 2
2 0
0 3
3 2
This is the most confusing part to me, as it seems to me that in the second input there should be solution. Obviously the maximal cycle in the graph will have infinite number of edges. Consider a cycle that goes 0 - 1 - 2 - 0 - 3 - 2 - 0. Is it the maximal? No. So it makes me think by the maximal cycle problem setter means the cycle that goes through each edge only once, and "the" must be indicating that there must be only 1 such cycle. Hence, the solution to this problem is very simple - just check that all in-degrees and out-degrees are equal to one. Problem with that is that it seems too easy, and my solution gives WA.
[[ Note that there shouldn't not be more than one connected component in the input Graph graph, as it would result in non DAG and would contradict to the input Discrption ]]] ()
I'm clearly not understanding what the problem wants us to find here.
So What is DAGy ???
--
Aminreza Gholami
سلام،
نکته اول اینکه دنباله راس های
0-1-2-0-3-2-0 تشکیل یک cycle نمیدهند. بلکه به ای دنباله یک walk میگوییم. کلا cycle راس تکراری ندارد.(برای تعریف دقیق تر
میتونید کتاب گراف وست رو یه نگاه بندازید:دی)
من از روی کلمه the نمیگم که یک دور ماکسیال وجود داره
اما میشه ثابت کرد که اگر دور همیلتونی توی گراف مساله وجود داشته
این دور یکتاست.
کلا در مورد چیزهایی که صورت مساله به
طور صریح و واضح نگفته تا وقتی که برای خودتون ثابت نکردید استفاده نکنید و دنبال استفاده
از قواعد گرامری برای حل مساله نباشید! مسابقه ی ادبیات نیست. :دی
در ضمن به نظر من راه حلتون هم اشتباه
هست .روی این تست چه جوری جواب میده؟
5 6
0 1
1 2
2 3
3 4
4 0
1 3
تعریف dagy هم در صورت سوال امده و فکر کنم کاملا واضح هست ابتدا یک dag برای خودت بکش(یعنی یک گراف جهت دار بدون دور)بعد یک یال دلخواه بهش اضافه کن.
--
You received this message because you are subscribed to the Google Groups "AUT-ACMICPC" group.
To post to this group, send email to aut-a...@googlegroups.com.
To unsubscribe from this group, send email to aut-acmicpc...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/aut-acmicpc?hl=en.
Angeh A2
DAGy is made up of a directed acyclic graph plus one additional directed edge. With this additional edge a cycle forms that goes through every vertex in the graph.
"
الان این مثالی که زدین
Dagyهست یا نه ؟
هنوز راه حال کاملی ندارم ، در واقع نفهمیدم
Dagy
چیه
--
ANGEH A2