Page 1 of 2

10462 - Is There A Second Way Left?

Posted: Sun Mar 16, 2003 4:44 pm
by ditrix
I don't know where I have a mistake... :(

I use the next algorithm:

Code: Select all

0. Make a graph with the vertex - neighbors and the edges - direct conections.

1. Launch DFS and calculate the number of visited vertex. If this number is different from number total of vertex: print "No way", return 
2.  If number of vertex is equal to number of edges + 1: print "No second way", return
3. Search the minimum covering tree and his price Pmin
4. For each edge  of the minimum covering tree do:
     4.1 Delete this edge from the graph
     4.2 Launch DFS and if the new graph isn't connexe go to 4.6 
     4.3  Search the minimum covering tree and his price P for this new graph
     4.4  If P==Pmin go to 5
     4.5 If P minimize the price of second-way-tree memorize it
     4.6 Undelete the edge
5. Print P, return
Is it correct ?

Posted: Mon Mar 17, 2003 1:56 am
by Adrian Kuegel
Do you consider this:
there may be multiple connections between two ends
For example the input:
1
3 4
1 2 1
2 3 1
1 3 3
1 3 4
Output is:
Case #1 : 4

My first program had the mistake that it printed 3 in this case.

Posted: Mon Mar 17, 2003 3:01 am
by ditrix
Yes, this case is ok, and all that concern the multiple connections seems to be all right.
I tested my program with many possible cases (v=1 or e=0 included), but I havn't fixed an error.

Am I right to suppose that if v=1 and for all e the answer is "No second way"?

Posted: Sat Apr 19, 2003 4:30 pm
by shohag sust cse
For this problem i consider following thing's but got WA:Look plz:
1.when i take the input i consider the lowest cost edge.
Like:
if 1 2 10
1 2 5
1 2 11
in this case i consider 5 and all the other store in a struct and finaly all the
extra cost sort according to there cost.i.e,
2 3 10
3 2 5
3 4 5
then the cost matrix will contain
1 2 5
2 3 5
3 4 5
now after sorting the struct i replace 1 2 5 by 1 2 10 because of second
mst.For this input out put will for minimum 15 and the second 20.Is my logic clear.Plz help me.
All time i
nv1=stru[0].v1
nv2=stru[0].v2;
len=stru[0].len;

and replace as

cost[nv1][nv2]=cost[nv2][nv1]=len;

Now Prims.
:oops:

10462 - Is There A Second Way Left ?

Posted: Fri Jul 04, 2003 8:04 pm
by mido
Is it correct that the problem here is to find the 2nd minimum spanning tree? I'd also aprreciate any tricky input - output set to check my code:

Code: Select all

#include <iostream.h>

struct node{
       int x;
       int y;
       int cost;
       bool change;
} edge[210];

long long t,cur,i,j,k,v,e,x,y,cost,lim,count,sum;
bool found1,found2;
int parent[150];

int findpar(int x)
{
    while (parent[x]!=-1)
          x=parent[x];
    return x;
}

void main()
{
     cin>>t;
     cur=0;
     while (++cur<=t)
     {
           cin>>v>>e;
           lim=0;
           found1=false;
           found2=false;
           j=1;

           for (i=1;i<=v+1;i++)
               parent[i]=-1;

           for (i=1;i<=e;i++)
           {
               cin>>x>>y>>cost;
               j=1;
               for (j=1;j<=lim && cost>=edge[j].cost;j++){}
               for (k=lim+1;k>=j+1;k--) edge[k]=edge[k-1];
               edge[j].x=x;
               edge[j].y=y;
               edge[j].cost=cost;
               edge[j].change=false;
               lim++;
           }

           cout<<"Case #"<<cur<<" : ";
           if (e<v-1) {cout<<"No way"<<endl;continue;}
           if (v==1) {cout<<"No second way"<<endl;continue;}

           lim=e;
           count=0;
           sum=0;
           i=1;

           while (count<v-1 && i<=lim)
           {
                 x=edge[i].x;
                 y=edge[i].y;

                 if (findpar(x)==findpar(y))
                 {i++;continue;}

                 count++;
                 edge[i].change=true;
                 parent[findpar(x)]=findpar(y);
                 sum+=edge[i].cost;
                 i++;
           }

           if (count==v-1) found1=true;
           if (e==v-1 && found1) {cout<<"No second way"<<endl;continue;}

           if (count==v-1)
           {
              int k=i-1;
              bool done=false;

              while (!done && k>0)
              {
                    if (!edge[k].change)
                    {k--;continue;}

                    for (i=1;i<=v+1;i++)
                        parent[i]=-1;

                    sum=0;
                    count=0;
                    i=1;

                    while (count<v-1 && i<=lim)
                    {
                          x=edge[i].x;
                          y=edge[i].y;

                          if (i==k || findpar(x) == findpar(y))
                          {i++;continue;}

                          count++;
                          parent[findpar(x)]=findpar(y);
                          sum+=edge[i].cost;
                          i++;
                    }

                    if (count==v-1) {found2=true;done=true;}
                    else k--;
              }
           }
           if (found2) cout<<sum<<endl;
           else if (found1) cout<<"No second way"<<endl;
           else cout<<"No way"<<endl;
     }
}

Posted: Tue Jun 22, 2004 1:13 pm
by miras
HM..

I think that ithis code is quite ... strange to udestand..

Can u explain it how does o\it work ??


Bcs. i can help u

Posted: Tue Jun 22, 2004 1:27 pm
by miras
HM..

I think that ithis code is quite ... strange to udestand..

Can u explain it how does o\it work ??


Bcs. i can help u

Posted: Wed Mar 22, 2006 5:08 pm
by lonelyone
My algorithm:

Code: Select all

1. using vector to store multi-edge graph
2. compute MST for the first mst distance
    a) if first distance doesn't exist, then output "No way", then exit
    b) if n==0 && m==0, output "NO way", then exit
    else continue
3. if n==m+1, output "No second way"
4. using first mst's parent path, scan the path again
    try to remove one edge from graph
    and do a second MST
    a) if second distance doesn't exist, then output "No second way", exit
    b) if second distance exist, then output the second distance
that's all
did I miss something, could someone give me so more test cases
please

lonely

Posted: Thu Mar 30, 2006 4:50 pm
by mido
by "try to remove one edge from graph" I presume one of the edges in the first MST, am I right? In that case, that should work(as far as I can remember...:) )..

Posted: Sun Apr 09, 2006 3:24 pm
by lonelyone
No one want to help us out... :cry:

Posted: Sun Apr 30, 2006 7:38 pm
by stubbscroll
Mido, your code fails this case:

Code: Select all

1
4 7
3 4 486
2 4 851
4 1 705
3 2 8
2 1 59
4 1 73
2 1 114
Your code outputs 553, the correct answer is 195.

Lonelyone, your algorithm looks correct. According to the problem description, there is no graph with 0 vertices in the input, so you need not check that (although I haven't tested this with assert yet). I can't confirm the correctness though, as I don't have AC yet.

Posted: Sat May 06, 2006 6:13 am
by lonelyone
Thanks for your reply.
I got the same result as you of your test case.
So, maybe I will examine my code for a while.
:cry:

Posted: Mon Mar 05, 2007 9:58 pm
by anouk
Could someone please post some tests? I followed the instructions on algorithmist.com, and for the test posted here my output is correct. I just can't see where I've made my mistake.

Test Cases please...

Posted: Sat May 05, 2007 10:16 pm
by nymo
I get correct answers for the inputs I 've found... Some more test cases needed. What is the catch? I am getting WAs :(
I 've entirely used 32-bit ints. Is it okay? No range for cost value is specified ...

Re: 10462 - Is There A Second Way Left ?

Posted: Wed Feb 04, 2009 4:01 pm
by pradeepr
I am getting WA

I tried to solve this problem by first finding a MST using kruskals and then finding the max[u,v] for all vertices u ,v in the MST and using this further to find the second MST.

MY code gives right outputs for all the test cases given above in this topic..
Can some check my code and please let me know of what is wrong with my code

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
typedef struct node
{
        struct node* head; //head of the disjoint set
        struct node* next; // next node of the disjoint set
        int label;
}node;

typedef struct edge
{
        int inlabel; //invertex label
        int outlabel;//outvertex label
        int weight;   //weight of the edge
        bool belongs; //indicates whether it belongs to MST or not
}edge;



void make_set(node &N) // makes a single node disjoint set
{
        N.head=&N;
        N.next=NULL;
}

node * find_set(node N) // returns the head of the list in which the node N is placed
{

        return N.head;
}

void find_union(node *a, node *b,map<node*,node*> &M) //union of 2 disjoint sets given their heads
{
        node *tail1=M[a];
        tail1->next=b;
        M.erase(b);
        while(b->next !=NULL)
        {
                b->head=a;
                b=b->next;
        }
        b->head=a;
        M[a]=b;
}


int compare(const void *a,const void *b) // compare function to sort the edges based on their weights
{
	edge x=*(edge*)a;
	edge y=*(edge*)b;
	if(x.weight >  y.weight)
		return 1;
	else
		return -1;
}

void DFS_FILL_MAX_VISIT(int u,int x,int size,int **G,vector<int>& max) // find an edge of max weight on the unique path  from u to every vertex v and stores it in max[v]
{
	for(int v=0;v<size;v++)
	{
		if( G[x][v]>0 && max[v]==0 && v!=u)
		{

			if(x==u ||( G[x][v] >max[x]))
				max[v]=G[x][v];
			else
				max[v]=max[x];

			DFS_FILL_MAX_VISIT(u,v,size,G,max);
		}
	}
}


int main()
{
	int num_cases,N,num_edges;
	int temp1,temp2;
	int temp3;
	cin >>num_cases;
	for(int k=0;k<num_cases;k++)
	{
		cin>>N;
		unsigned long w=0,w2=1000000;
		node *vertices=new node[N];
		cin>>num_edges;
		edge *edges=new edge[num_edges];

		map<node*,node*> M;
		node *head1,*head2;

		int ** G= new int*[N]; //MST to be built 
		for(int i=0;i<N;i++)
		{
			G[i]=new int[N];
			for(int j=0;j<N;j++)	//initialization.. an edge G[i][j]=0 implies there is no edge between vertices i and j
				G[i][j]=0;
		}	
		                  //using kruskals algorithm to build a MST
		for(int j=0;j<N;j++)
		{
			(vertices[j]).label=j;
			M[vertices+j]=vertices+j;  //linked list representation in which the map M is used to find the tail of list given the head  i.e M[head]=tail
			make_set(vertices[j]);      

		}

		temp3=0;
		for(int j=0;j<num_edges;j++)
		{
			cin>>temp1>>temp2>>temp3;
			edges[j].inlabel=temp1-1;
			edges[j].outlabel=temp2-1;
			edges[j].weight=temp3;
			edges[j].belongs=false;

		}
		qsort(edges,num_edges,sizeof(edge),compare);

		for(int j=0;j<num_edges;j++)
		{
			head1=find_set(vertices[edges[j].inlabel]);
			head2=find_set(vertices[edges[j].outlabel]);
			if(head1!=head2)
			{
				find_union(head1,head2,M);
				w+=edges[j].weight;
				edges[j].belongs=true;
				G[edges[j].outlabel][edges[j].inlabel]=G[edges[j].inlabel][edges[j].outlabel]=edges[j].weight;
			}
		}
		cout<<"Case #"<<k+1<<" : ";
		if(M.size()>1)
			cout<<"No way";
		else 
		{

			w2=1000000;
			for(int j=0;j<num_edges;j++)
			{
				int u,v;
				if(!edges[j].belongs)
				{
					vector<int> temp(N,0);
					u=edges[j].inlabel;
					v=edges[j].outlabel;
					DFS_FILL_MAX_VISIT(u,u,N,G,temp);
					if( (edges[j].weight-temp[v])< w2)
					{
						w2=(edges[j].weight-temp[v]);
					}
				}
			}
			if(w2==1000000)
				cout<<"No second way";
			else
				cout<<w+w2;
		}
			cout<<'\n';
	}
	return(0);
}