Page 1 of 1
11893 - Fabulous DAGy
Posted: Mon Nov 01, 2010 2:06 am
by Leonid
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?
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 01, 2010 7:11 am
by Angeh
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 ...
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 01, 2010 10:59 am
by Leonid
Thanks Angeh, that explains the problem pretty much
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 01, 2010 5:22 pm
by wazaaaap
So you should find the cycle which is equal to the number of vertices by visiting them at most once?
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 01, 2010 5:33 pm
by Angeh
yes ... or maybe somthing easier ... Find a longest Path of size n ...
11893 - Fabulous DAGy WHY WA??????
Posted: Wed Nov 03, 2010 3:22 pm
by shibly
Why WA?
Someone Please check my code
or give me some input/output....
thanks all.
Code: Select all
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>adj[400];
int col[400],dis[400],K=0,par[400];
int DFS(int u)
{
col[u]=1;
for(int i=0;i<(int)adj[u].size();i++)
{
if(!adj[u][i]) dis[u]>?=1; //if adj[u][i] is source
else if(col[adj[u][i]]==0) dis[u]>?=1+DFS(adj[u][i]);
else if(col[adj[u][i]]==2) dis[u]>?=1+dis[adj[u][i]];
}
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++)
{
adj[i].clear();
dis[i]=col[i]=0;
}
while(m--)
{
scanf("%d%d",&u,&v);
adj[u].push_back(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;
}
Re: 11893 - Fabulous DAGy
Posted: Wed Nov 03, 2010 3:29 pm
by Angeh
// 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 ..
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 08, 2010 12:15 pm
by jurong
Can you hint me how to Remove the Extra Edge ?
Re: 11893 - Fabulous DAGy
Posted: Mon Nov 08, 2010 12:49 pm
by Angeh
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
Re: 11893 - Fabulous DAGy
Posted: Sun Jan 09, 2011 2:20 am
by wazaaaap
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.
Re: 11893 - Fabulous DAGy
Posted: Fri Jan 21, 2011 10:57 am
by MRH
Hi wazaaaap
try to sloved this problem O( N ( M+N ) ) with respect to some condition.
hope it help you.