10462 - Is There A Second Way Left?

Chirag Chheda · Post by **Chirag Chheda** » Fri Feb 27, 2009 10:31 pm

Well Initially I got several WA for this prob but later i found a case which my code was not handling properly which helped me 2 get an ACC. Hope it helps u.

Input:

Code: Select all

Output is 2 obviously.

pradeepr · Post by **pradeepr** » Sat Feb 28, 2009 1:15 pm

Thanks for your help
But my code gives the same answer as u have mentioned for the above input.. though the online judge gives a WA

Chirag Chheda · Post by **Chirag Chheda** » Sun Mar 01, 2009 12:49 pm

Well in that case it would be better if u post ur code and explain ur algo.
Thanx.

pradeepr · Post by **pradeepr** » Mon Mar 09, 2009 3:38 pm

hey.. thanks for the help..my code is attached in my first post in the previous page.Please go through it .My algo also has been briefly explained there though I would like to explain in detail.

I am using kruska's algorithm to find the MST.If the number of components after running kruskals is greater than 1,then there exists no MST and I output the result accordingly.
if MST exists,then I look for 2nd minimum spanning tree.I used the algorithm suggested in cormen for this.
all the edges (u,v) part of the graph and not present in the MST will be added to the MST one at a time and the maximum edge on the resultant cycle is removed.This operation make the resultant structure a tree.
Of all such possibles trees ,I choose the tree with minimum weight sum.

Please go through my code ang suggest me something as to what is wrong with it.

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);
}

Chirag Chheda · Post by **Chirag Chheda** » Mon Mar 09, 2009 6:50 pm

all the edges (u,v) part of the graph and not present in the MST will be added to the MST one at a time and the maximum edge on the resultant cycle is removed.This operation make the resultant structure a tree.

I doubt if your this part is correct or not. However I can tell you my algo for the second part. Remove one edge at a time from the above MST and then find the value of the resulting MST. After doing this for all the edges present in the first MST find the one with the minimum value.

Hope it helps.

pradeepr · Post by **pradeepr** » Tue Mar 10, 2009 3:31 pm

This one was same as the problem 10600.My algo was the same for both and my solution for 10600 got accepted.
I followed the algo give in cormen to generate the second MST.
Please post some input cases that might be crucial in judging where my solution goes wrong.

Jehad Uddin · Post by **Jehad Uddin** » Sat Oct 03, 2009 2:01 am

Try this cases,
Input

Code: Select all

Output

Code: Select all

Case #1 : No second way
Case #2 : 8

Raihan92 · Post by **Raihan92** » Sun Mar 25, 2012 7:39 pm

Why WA??? Need some test cases why wrong...totally confused

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<cstdlib>
#define MAXS 10600
#define INFINITY 100000000
using namespace std;
#define REP(i,n) for (i=0;i<n;i++)
#define PI (2*acos(0))
#define ERR 1e-5
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back

struct airport
{
    int x,y,cost;
};

airport EDGE[MAXS];
int find_representative(int r);
bool compare(const airport& a, const airport& b);
int parent[MAXS],CMST[MAXS];
bool mark[MAXS];

int main()
{
    int i,j,k,l,t,u,v,RE_F1,RE_F2,TEST,N,M,T_COST,temp,sum,MIN,A,B;
    scanf("%d",&TEST);
    for(t=1; t<=TEST; t++)
    {
        memset(parent,0,sizeof(parent));
        memset(EDGE,0,sizeof(EDGE));
        memset(mark,0,sizeof(mark));
        memset(CMST,0,sizeof(CMST));
        scanf("%d %d",&N,&M);
        if(N==0&&M==0)
        {
            printf("Case #%d : No way\n",t);
            continue;
        }
        for(i=1; i<=M; i++)
        {
            scanf("%d %d %d",&EDGE[i].x,&EDGE[i].y,&EDGE[i].cost);
            //printf("%d %d %d\n",EDGE[i].x,EDGE[i].y,EDGE[i].cost);
        }
        A = M + 1;
        sort(EDGE,EDGE+A,compare);

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

        sum = 0;
        T_COST = 0;
        k = 1;

        for(i=1; i<=M; i++)
        {
            u = EDGE[i].x;
            v = EDGE[i].y;
            RE_F1 = find_representative(u);
            RE_F2 = find_representative(v);

            if(RE_F1!=RE_F2)
            {
                parent[RE_F1] = RE_F2;
                sum += EDGE[i].cost;
                mark[i] = true;
            }
        }

        B = parent[1];

        for(i=2; i<=N; i++)
        {
            if(B!=parent[i]&&M!=1)
            {
                sum = INFINITY;
            }
        }

        for(i=1; i<=M; i++)
        {
            if(mark[i]==true)
            {
                for(l=1; l<=N; l++)
                    parent[l] = l;

                for(j=1; j<=M; j++)
                {
                    if(j!=i)
                    {
                        u = EDGE[j].x;
                        v = EDGE[j].y;
                        RE_F1 = find_representative(u);
                        RE_F2 = find_representative(v);

                        if(RE_F1!=RE_F2)
                        {
                            //cout<<EDGE[j].cost<<endl;
                            parent[RE_F1] = RE_F2;
                            T_COST += EDGE[j].cost;
                        }
                    }
                }
                //cout << T_COST << endl;
                CMST[k] = T_COST;
                k++;
                T_COST = 0;
                mark[i] = true;
            }
        }
        k--;
        MIN = INFINITY;
        for(i=1; i<=k; i++)
        {
            if(CMST[i]<MIN&&sum<=CMST[i]) MIN = CMST[i];
        }
        if(MIN==INFINITY&&sum==INFINITY) printf("Case #%d : No way\n",t);
        else if(MIN==INFINITY&&sum!=INFINITY) printf("Case #%d : No second way\n",t);
        else printf("Case #%d : %d\n",t,MIN);
    }
    return 0;
}
bool compare(const airport& a, const airport& b)
{
    return a.cost < b.cost;
}

int find_representative(int r)
{
    if(parent[r]==r)
        return r;
    else
    {
        return parent[r] = find_representative(parent[r]);
    }
}

brianfry713 · Post by **brianfry713** » Tue Mar 27, 2012 11:58 pm

Try the input in the post before yours.

raihan_sust05 · Post by **raihan_sust05** » Wed Feb 12, 2014 5:19 pm

getting WA!!!

pls anyone help me .....here is my code :

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>


#define pi acos(0)
#define inf 20000000000
#define max 10000
#define sz 100
#define true 1
#define false 0
#define pb(a) push_back(a)
#define size(e) (int)e.size()
#define clr(a,b) memset(a,b,sizeof(a))

//ll rw[10] = {0,0,1,-1};
//ll cl[10] = {1,-1,0,0};   /*array for 4-sides move*/

//ll drw[10] = {1,-1,1,-1};
//ll dcl[10] = {1,1,-1,-1}; /*array for diagonal 4-sides move*/

//ll rw[10] = {0,0,1,1,-1,-1};
//ll cl[10] = {1,-1,1,0,-1,0};   /*array for 6-sides move*/

//ll rw[10] = {0,0,1,1,1,-1,-1,-1};
//ll cl[10] = {1,-1,1,0,-1,-1,0,1};   /*array for 8-sides move*/

//ll rw[10] = {0,0,1,-1, 0, 0};
//ll cl[10] = {1,-1,0,0, 0, 0};
//ll hi[10] = {0, 0 ,0, 0, 1, -1}; /*array for 3-D move */

typedef long long int ll;

struct edge
{
    ll u, v, c;

    bool operator <(const edge& p)const
    {
        return c < p.c;
    }
};



using namespace std;

ll num, m, par[max], mcost, scost, costs[max], got[max];
vector <edge> e;

ll mst();
ll omst(ll a);
ll find(ll a);

int  main()
{
    ll i, j, n, cas = 1, tst;
    edge bin;

    scanf("%lld", &tst);

    while(cas <= tst)
    {
        e.clear();
        clr(got, 0);

        scanf("%lld %lld", &num, &m);

        for(i = 0; i < m; ++i)
        {
            scanf("%lld %lld %lld", &bin.u, &bin.v, &bin.c);
            e.pb(bin);

        }

        mcost = 0;

        for(i = 1; i <= num; ++i)
            par[i] = i;

        for(i = 0; i < size(e); ++i)
        costs[i] = inf;

        ll c = 0;

        c =  mst();

        printf("Case #%lld : ", cas);

        scost = 0;

        if(c == num - 1)
        {
            n = 0;

            for(i = 0; i < size(e); ++i)
            {
                for(j = 1; j <= num; ++j)
                    par[j] = j;

                if(got[i])
                {
                    costs[i] = 0;
                    c = omst(i);

                    if(c < num - 1 || costs[i] < mcost)
                        costs[i] = inf;

                    if(c == num - 1 && costs[i] >= mcost)
                        ++n;
                }
            }

              if(n == 0)
                puts("No second way");

              else
               {
                 scost = *min_element(costs, costs + m);
                 printf("%lld\n", scost);
               }
        }

            else
            puts("No way");

            ++cas;
        }
        return 0;
}

    ll mst()
    {
        ll i, j, n, p;
        ll c = 0;

        sort(e.begin(), e.end());

        for(i = 0 ; i < size(e); ++i)
        {
            ll u = find(e[i].u);
            ll v = find(e[i].v);

            if(u != v)
            {
                par[v] = u;
                ++c;

                got[i] = true;

                mcost += e[i].c;

                if(c == num - 1)
                    break;

            }
        }

        return c;
    }

    ll omst(ll a)
    {
        ll i, j, n, p;
        ll c = 0;

        sort(e.begin(), e.end());

        for(i = 0 ; i < size(e); ++i)
        {
            ll u = find(e[i].u);
            ll v = find(e[i].v);

            if(u != v && i != a)
            {
                par[v] = u;
                ++c;

                costs[a] += e[i].c;

                if(c == num - 1)
                    break;

            }

        }

        return c;
    }

    ll find(ll a)
    {
        if(par[a]== a)
            return(a);

        return(par[a] = find(par[a]));
    }

brianfry713 · Post by **brianfry713** » Wed Feb 12, 2014 9:34 pm

Input:

Code: Select all

AC output:

Code: Select all

Case #1 : 13092
Case #2 : No way
Case #3 : 3088
Case #4 : No way
Case #5 : No way
Case #6 : 3960
Case #7 : No way
Case #8 : 136
Case #9 : No way
Case #10 : No way
Case #11 : 3361
Case #12 : No way
Case #13 : No way
Case #14 : 5977
Case #15 : No way
Case #16 : No way
Case #17 : 12337
Case #18 : 1336
Case #19 : 5028
Case #20 : 1938

brianfry713 · Post by **brianfry713** » Mon Oct 06, 2014 9:49 pm

Input:

Code: Select all

AC output:

Code: Select all

Case #1 : 0

saeedcsedu · Post by **saeedcsedu** » Sat Oct 25, 2014 11:42 am

why wrong answer:
my code:

Code: Select all

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int flag=0,flag1=0;
int par[105],v,cost=0,t=0;
struct data
{
    int node1,node2;
    int weight;
     bool operator < (const data &p) const
    {
        return (weight>p.weight);
    }
};
priority_queue <data> q,q_a;
priority_queue <data> q1;
int find(int r)
{
    if(par[r]==r)  return r;
    else
        return find(par[r]);
}
void mst()
{   int j=0,a,b;
    for(int i=1;i<=v;i++) par[i]=i;
    cost=0;
    while(!q.empty())
    {
        data s;
        s=q.top();
        q.pop();
        a=find(s.node1);
        b=find(s.node2);
        if(a!=b)
        {
            par[a]=b;
            j++;
            cost+=s.weight;
            q1.push(s);
        }
        if(j==v-1) break;
    }
}
void mst1(data s1)
{   int j=0,a,b;
    for(int i=1;i<=v;i++) par[i]=i;
    cost=0;
    while(!q.empty())
    {
        data s;
        s=q.top();
        q.pop();
        if(s1.node1==s.node1&&s1.node2==s.node2&&s1.weight==s.weight) continue;
        a=find(s.node1);
        b=find(s.node2);
        if(a!=b)
        {
            par[a]=b;
            j++;
            cost+=s.weight;
        }
        if(j==v-1) break;
    }
    return;
}
int main()
{

    int e,i,j,a,b,wei,c1,c2,te,k;
    cin>>te;
    for(k=1;k<=te;k++)
    {
        cin>>v>>e;
        while(!q.empty()) q.pop();
        while(!q_a.empty()) q_a.pop();
        while(!q1.empty()) q1.pop();
        for(i=0;i<e;i++)
        {
            cin>>a>>b>>wei;
            data s;
            s.node1=a;
            s.node2=b;
            s.weight=wei;
            q.push(s);
        }
        q_a=q;
        mst();
        j=0;
        for(i=1;i<=v;i++) if(par[i]==i) j++;
        if(j>1) cout<<"Case #"<<k<<" : No way"<<endl;
        else if(v>e) cout<<"Case #"<<k<<" : No second way"<<endl;
        else
        {
            c1=cost;
            c2=10000000;
            while(!q1.empty())
            {
                data s=q1.top();
                q1.pop();
                while(!q.empty()) q.pop();
                q=q_a;
                int cnt=0;
                mst1(s);
                for(i=1;i<=v;i++) if(par[i]==i) cnt++;
                if(cnt>1) continue;
                if(c2>cost) c2=cost;
            }
                if(c2==10000000) c2=c1;
                cout<<"Case #"<<k<<" : "<<c2<<endl;
        }
    }
    return 0;
}

brianfry713 · Post by **brianfry713** » Wed Oct 29, 2014 10:56 pm

Input:

Code: Select all

AC output:

Code: Select all

Case #1 : No second way

ainan.ahmed · Post by **ainan.ahmed** » Sun Jan 08, 2017 1:05 pm

Can anyone tell me why i am getting WA??

Tried all the testcase given in this forum & udebug..they all gave correct ans.
my code: http://ideone.com/m5lFmo

OJ Board

10462 - Is There A Second Way Left?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

WA: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left ?

Re: 10462 - Is There A Second Way Left?

Re: 10462 - Is There A Second Way Left?

Re: 10462 - Is There A Second Way Left?

Re: 10462 - Is There A Second Way Left?