Pagini recente » Cod sursa (job #2455822) | Cod sursa (job #1725283) | Cod sursa (job #2479325) | Cod sursa (job #1057616) | Cod sursa (job #2669701)
#include <bits/stdc++.h>
using namespace std;
ifstream in("lazy.in");
ofstream out("lazy.out");
typedef long long ll;
const int lim=2e5+4;
struct Op
{
int x;
int y;
ll c1;
ll c2;
int ind;
};
vector<Op> edges;
bool ok[lim];
bool mycmp(Op a,Op b)
{
if(a.c1==b.c1)
return a.c2>b.c2;
return a.c1<b.c1;
}
int link[lim];
int dim[lim];
int tata(int x)
{
int cpy=x,aux;
while(x!=link[x]) x=link[x];
while(cpy!=link[cpy]) aux=cpy,cpy=link[cpy],link[aux]=x;
return x;
}
void unite(int x,int y,int ind)
{
x=tata(x);
y=tata(y);
if(x==y) return ;
ok[ind]=true;
if(dim[x]<dim[y]) swap(x,y);
dim[x]+=dim[y];
link[y]=x;
}
int main()
{
int n,m,x,y;
ll c1,c2;
in>>n>>m;
for(int i=1;i<=n;++i)
link[i]=i,dim[i]=1;
for(int i=1;i<=m;++i)
{
in>>x>>y>>c1>>c2;
edges.push_back({x,y,c1,c2,i});
}
sort(edges.begin(),edges.end(),mycmp);
for(auto e:edges)
unite(e.x,e.y,e.ind);
for(int i=1;i<=m;++i)
if(ok[i]) out<<i<<'\n';
return 0;
}