Pagini recente » Cod sursa (job #2009610) | Cod sursa (job #1219868) | Cod sursa (job #1764514) | Cod sursa (job #1124591) | Cod sursa (job #2028520)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
long long n,m,i,l,a,b,c1,c2,x,y,rx,ry;
long long w[200005],sol[200005];
pair < pair <long long,long long> ,pair <long long, pair <long long,long long> > > v[200005];
long long f(long long k){
while(w[k]>0){
k=w[k];
}
return k;
}
int main(){
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>a>>b>>c1>>c2;
v[i].first.first=c1;
v[i].first.second=-c2;
v[i].second.first=a;
v[i].second.second.first=b;
v[i].second.second.second=i;
}
sort(v+1,v+m+1);
for(i=1;i<=n;i++){
w[i]=-1;
}
l=0;
for(i=1;i<=m;i++){
x=v[i].second.first;
y=v[i].second.second.first;
rx=f(x);
ry=f(y);
if(rx!=ry){
sol[++l]=v[i].second.second.second;
if(w[rx]<w[ry]){
w[rx]+=w[ry];
w[ry]=rx;
}
else{
w[ry]+=w[rx];
w[rx]=ry;
}
}
}
for(i=1;i<=l;i++){
fout<<sol[i]<<"\n";
}
return 0;
}