Pagini recente » Cod sursa (job #3000079) | Cod sursa (job #134618) | Cod sursa (job #213570) | Cod sursa (job #1593397) | Cod sursa (job #2029845)
#include <fstream>
#include <algorithm>
#define DIM 200002
using namespace std;
long long n,m,i,x,y,k,rx,ry,t[DIM],sol[DIM];
pair < pair<long long,long long>, pair < long long , pair <long long,long long> > > v[DIM];
long long rad (long long x){
while (t[x] > 0)
x = t[x];
return x;
}
int main (){
ifstream fin ("lazy.in");
ofstream fout ("lazy.out");
fin>>n>>m;
for (i=1;i<=n;i++)
t[i] = -1;
for (i=1;i<=m;i++){
fin>>v[i].second.first>>v[i].second.second.first>>v[i].first.first>>v[i].first.second;
v[i].second.second.second = i; // indicele
}
sort (v+1,v+m+1);
for (i=1;i<=m;i++){
x = v[i].second.first;
y = v[i].second.second.first;
rx = rad (x);
ry = rad (y);
if (rx != ry){
// unesc x cu y
k++;
sol[k] = v[i].second.second.second;
if (t[rx] < t[ry]){
t[rx] += t[ry];
t[ry] = rx;
}
else{
t[ry] += t[rx];
t[rx] = ry;
}
}
}
for (i=1;i<=k;i++)
fout<<sol[i]<<"\n";
return 0;
}