Pagini recente » Cod sursa (job #2999112) | Cod sursa (job #1682362) | Cod sursa (job #2055165) | Cod sursa (job #1572047) | Cod sursa (job #708345)
Cod sursa(job #708345)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
typedef long long i64;
struct str
{
int a,b,i;
i64 x,y;
};
struct str_cmp
{
bool operator()(str x,str y)
{
if (x.x==y.x)
return x.y>y.y;
else
return x.x<x.y;
};
};
const int N_MAX=200000;
int r[N_MAX+1],sol[N_MAX];
str e[N_MAX+1];
void upd_r(int x)
{
stack <int> s;
while (r[r[x]]!=r[x])
{
s.push(x);
x=r[x];
}
while (!s.empty())
{
r[s.top()]=r[x];
s.pop();
}
}
int main()
{
int n,m;
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)
{
e[i].i=i;
scanf("%d%d%lld%lld",&e[i].a,&e[i].b,&e[i].x,&e[i].y);
}
sort(e+1,e+m+1,str_cmp());
for (int i=1;i<=n;++i)
r[i]=i;
for (int i=1;i<=m;++i)
{
int x=e[i].a,y=e[i].b;
upd_r(x);
upd_r(y);
if (r[x]!=r[y])
{
++sol[0];
sol[sol[0]]=e[i].i;
r[r[x]]=r[y];
}
}
sort(sol+1,sol+n);
for (int i=1;i<n;++i)
printf("%d\n",sol[i]);
return 0;
}