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