11893 - Fabulous DAGy

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11893 - Fabulous DAGy

Post by Leonid » Mon Nov 01, 2010 2:06 am

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

Post by Angeh » Mon Nov 01, 2010 7:11 am

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

Post by Leonid » Mon Nov 01, 2010 10:59 am

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

Post by wazaaaap » Mon Nov 01, 2010 5:22 pm

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

Post by Angeh » Mon Nov 01, 2010 5:33 pm

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??????

Post by shibly » Wed Nov 03, 2010 3:22 pm

Why WA?
Someone Please check my code
or give me some input/output.... :oops:
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;
}





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

Re: 11893 - Fabulous DAGy

Post by Angeh » Wed Nov 03, 2010 3:29 pm

// 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

Post by jurong » Mon Nov 08, 2010 12:15 pm

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

Post by Angeh » Mon Nov 08, 2010 12:49 pm

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

Post by wazaaaap » Sun Jan 09, 2011 2:20 am

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

Post by MRH » Fri Jan 21, 2011 10:57 am

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

hope it help you.

Post Reply

Return to “Volume 118 (11800-11899)”