#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
vector< pair< pair < int,int > ,int > > edge,ans; //edge x,y,weight
map< int, vector<int> > group; //groupno --> groupelement
vector<int> node(1001,0); //number of nodes maximum 1000;
bool comp(pair< pair <int,int > ,int > A,pair< pair <int ,int > ,int > B)
{
if(A.second< B.second)
return true;
else
return false;
}
int main()
{
int cgroup=1,m;
int n,x,y,w,e=0;
cin>>n>>m; //m - no of nodes
for(int i=0;i<n;i++)
{
cin>>x>>y>>w;
edge.push_back(make_pair(make_pair(x,y),w));
}
sort(edge.begin(),edge.end(),comp);
int k=0;
while(e<n-1)
{
x=edge[k].first.first,y=edge[k].first.second,w=edge[k].second;
if(node[x]==0&&node[y]==0)
{
ans.push_back(make_pair(make_pair(x,y),w));
group[cgroup].push_back(x);
group[cgroup].push_back(y);
node[x]=cgroup;
node[y]=cgroup;
cgroup++;
e++;
}
else if(node[x]!=0&&node[y]!=0)
{
if(node[x]>node[y])
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[y];
node[y]=node[x];
for(int i=0;i<group[tempgrp].size();i++)
{
int elem=group[tempgrp][i];
node[elem]=node[x];
group[node[x]].push_back(elem);
}
}
else if(node[x]<node[y])
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[x];
node[x]=node[y];
for(int i=0;i<group[tempgrp].size();i++)
{
int elem=group[tempgrp][i];
node[elem]=node[y];
group[node[y]].push_back(elem);
}
}
}
else if(node[x]!=0&&node[y]==0)
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[x];
group[tempgrp].push_back(y);
node[y]=node[x];
}
else if(node[x]==0&&node[y]!=0)
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[y];
node[x]=node[y];
group[tempgrp].push_back(x);
}
k++;
}
int grp=node[1];
for(int i=0;i<ans.size();i++)
cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
}
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
vector< pair< pair < int,int > ,int > > edge,ans; //edge x,y,weight
map< int, vector<int> > group; //groupno --> groupelement
vector<int> node(1001,0); //number of nodes maximum 1000;
bool comp(pair< pair <int,int > ,int > A,pair< pair <int ,int > ,int > B)
{
if(A.second< B.second)
return true;
else
return false;
}
int main()
{
int cgroup=1,m;
int n,x,y,w,e=0;
cin>>n>>m; //m - no of nodes
for(int i=0;i<n;i++)
{
cin>>x>>y>>w;
edge.push_back(make_pair(make_pair(x,y),w));
}
sort(edge.begin(),edge.end(),comp);
int k=0;
while(e<n-1)
{
x=edge[k].first.first,y=edge[k].first.second,w=edge[k].second;
if(node[x]==0&&node[y]==0)
{
ans.push_back(make_pair(make_pair(x,y),w));
group[cgroup].push_back(x);
group[cgroup].push_back(y);
node[x]=cgroup;
node[y]=cgroup;
cgroup++;
e++;
}
else if(node[x]!=0&&node[y]!=0)
{
if(node[x]>node[y])
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[y];
node[y]=node[x];
for(int i=0;i<group[tempgrp].size();i++)
{
int elem=group[tempgrp][i];
node[elem]=node[x];
group[node[x]].push_back(elem);
}
}
else if(node[x]<node[y])
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[x];
node[x]=node[y];
for(int i=0;i<group[tempgrp].size();i++)
{
int elem=group[tempgrp][i];
node[elem]=node[y];
group[node[y]].push_back(elem);
}
}
}
else if(node[x]!=0&&node[y]==0)
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[x];
group[tempgrp].push_back(y);
node[y]=node[x];
}
else if(node[x]==0&&node[y]!=0)
{
ans.push_back(make_pair(make_pair(x,y),w));
e++;
int tempgrp=node[y];
node[x]=node[y];
group[tempgrp].push_back(x);
}
k++;
}
int grp=node[1];
for(int i=0;i<ans.size();i++)
cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
}
No comments:
Post a Comment