Pagini recente » Cod sursa (job #385505) | Cod sursa (job #2256560) | Cod sursa (job #2855231) | Cod sursa (job #2726367) | Cod sursa (job #2955318)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
class sets {
private:
int t[200001];
public:
sets()
{
for (int i = 1; i <= 200000; i++)
t[i] = i;
}
int root(int x)
{
if (t[x] == x)
return x;
else
return t[x] = root(t[x]);
}
void unit(int x, int y)
{
t[root(x)] = root(y);
}
bool connected(int x, int y)
{
return root(x) == root(y);
}
};
int n, m;
sets S;
struct edge {
int x, y, poz, c1, c2;
bool operator < (edge aux)
{
if (c1 < aux.c1)
return true;
else if (c1 == aux.c1 && c2 > aux.c2)
return true;
return false;
}
}v[200001];
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> v[i].x >> v[i].y >> v[i].c1 >> v[i].c2;
v[i].poz = i;
}
sort(v + 1, v + m + 1);
for (int i = 1; i <= m; i++)
if (!S.connected(v[i].x, v[i].y))
fout << v[i].poz << '\n', S.unit(v[i].x, v[i].y);
return 0;
}