Hello everyone,Question is something like this:: We are given the adjacency matrix for a graph of n vertices(n<=1000) and we need to find the number of edges we need to delete in order to make it a tree.I did this question by applying kruskal's algorithm and I passed all the cases but I can't convince myself that I did correct.I feel as if it was just a blind shot.Can anybody assure me about the correctness or give some other approach to solve this.
My code looks like this.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nline cout<<"\n"
#define fast ios_base::sync_with_stdio(false)cin.tie(0)
#define ain(A, B, C) assert(IN(A, B, C))
#define ull unsigned long long int
#define ll long long int
#define pii pair<int,int>
#define MAXX 1009
#define fr(a,b,i) for(int i=a;i<b;i++)
vector<int>G[MAXX];
int a[MAXX][MAXX],cnt=0;
int parent[MAXX],r[MAXX],n;
int find_p(int v){
return (parent[v]==v?v:parent[v]=find_p(parent[v]));
}
void unionme(int a,int b)
{
if(r[a]>r[b]){
parent[b]=a;
}
else{
parent[a]=b;
}
if(r[a]==r[b]){
++r[a];
}
}
void kruskal()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j] or a[j][i]){
int aa=find_p(i);
int bb=find_p(j);
if(aa!=bb){
unionme(aa,bb);
a[i][j]=a[j][i]=0;
}
else
{
cnt++;
a[i][j]=0;
a[j][i]=0;
}
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)parent[i]=i,r[i]=0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
kruskal();
cout<<cnt<<endl;
return 0;
}
Full text and comments »