Cod sursa(job #547737)

Utilizator ProtomanAndrei Purice Protoman Data 6 martie 2011 17:45:01
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 200010
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m;
int t[MAX];
pair <pair <ll, ll>, pair <pair <int, int>, int> > c[MAX];

inline int tata(int x)
{
    if (t[x] != x)
        t[x] = tata(t[x]);

    return t[x];
}

int main()
{
	freopen("lazy.in", "r", stdin);
	freopen("lazy.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %lld %lld", &c[i].s.f.f, &c[i].s.f.s, &c[i].f.f, &c[i].f.s);

        c[i].f.s = -c[i].f.s;
        c[i].s.s = i;
    }

    sort(c + 1, c + 1 + m);

    for (int i = 1; i <= n; i++)
        t[i] = i;

    vector <int> vctSol;
    for (int i = 1; i <= m; i++)
    {
        if (tata(c[i].s.f.f) != tata(c[i].s.f.s))
        {
            t[tata(c[i].s.f.f)] = tata(c[i].s.f.s);

            vctSol.pb(c[i].s.s);
        }
    }

    sort(vctSol.begin(), vctSol.end());

    printf("%d", vctSol[0]);
    for (int i = 1; i < vctSol.size(); i++)
        printf(" %d", vctSol[i]);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}