## 11893 - Fabulous DAGy

Moderator: Board moderators

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### 11893 - Fabulous DAGy

Does anyone understand what this problem asks for?
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.
It is guaranteed that each input graph is a directed acyclic graph with one additional edge between two distinct vertices of graph.
The first quote claims that there is "one additional edge" that forms a cycle and if that edge didn't exist there wouldn't be a cycle. The second quote doesn't exactly say anything about additional edge resulting in a cycle, however does it mean so?
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 graph, as it would result in non DAG and would contradict to the second quote.

I'm clearly not understanding what the problem setter wanted us to find here. What do you guys think we have to find in this problem?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11893 - Fabulous DAGy

Check this .....
5 6
0 1
1 2
2 3
3 4
4 0
1 3
It's a Dagy ...
now i think its Easy To solve the Problem ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11893 - Fabulous DAGy

Thanks Angeh, that explains the problem pretty much

wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11893 - Fabulous DAGy

So you should find the cycle which is equal to the number of vertices by visiting them at most once?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11893 - Fabulous DAGy

yes ... or maybe somthing easier ... Find a longest Path of size n ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

shibly
New poster
Posts: 5
Joined: Wed Sep 22, 2010 7:32 am

### 11893 - Fabulous DAGy WHY WA??????

Why WA?
or give me some input/output....
thanks all.

Code: Select all

``````
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int col[400],dis[400],K=0,par[400];

int DFS(int u)
{
col[u]=1;
{
}
col[u]=2;
return dis[u];
}

int main()
{
int i,u,v,n,m,T;

//freopen("in1.in","r",stdin);

scanf("%d",&T);

while(T--)
{
scanf("%d%d",&n,&m);
if(n==1)    while(true);
for(i=0;i<n;i++)
{
dis[i]=col[i]=0;
}

while(m--)
{
scanf("%d%d",&u,&v);
}

m = DFS(0); //  This DFS calculate maximum cycle length.

if(m==n)    printf("Yeah, I'm superman\n");
else printf("Your DAGy was initially defected!\n");
}

return 0;
}

``````

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11893 - Fabulous DAGy

// This DFS calculate maximum cycle length.
From this line in your code i think your algorithm is wrong
you should not find a Cycle ... you should Remove the Extra Edge and then Find the Lenght of the DAG ..
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

jurong
New poster
Posts: 6
Joined: Wed Oct 06, 2010 1:05 pm

### Re: 11893 - Fabulous DAGy

Can you hint me how to Remove the Extra Edge ?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11893 - Fabulous DAGy

Just try to Remove all possible Edges ... and check if the Graph is DAG ... and if there is a path that Goes trough all vertexes or not
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11893 - Fabulous DAGy

Hey, when all nodes degree is 1 i automatically output "I am superman", or when there is one node with 2 degree, i check if it makes it acyclic by visiting the first node, and then the second node?

This code gives me TLE http://codepad.org/MJ3c9OGF (in this code the first theory, when all nodes degree is 1 is excluded, because i didn't realize that while coding). I think I'm missing some case to check the graph if it's DAGy or not.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11893 - Fabulous DAGy

Hi wazaaaap
try to sloved this problem O( N ( M+N ) ) with respect to some condition.