Cod sursa(job #2069963)

Utilizator cojocarugabiReality cojocarugabi Data 19 noiembrie 2017 00:26:13
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
class DSU
{
    public:
    int * f;
    int * sz;
    stack < pair < int* , int > > v;
    public:
    void init(int n)
    {
        f = new int[n + 5];
        sz = new int[n + 5];
        for (int i = 0;i < n + 5;++i)
            f[i] = 0;
        for (int i = 1;i <= n;++i)
            f[i] = i,sz[i] = 1;
    }
    int get(int k)
    {
        return k == f[k] ? k : get(f[k]);
    }
    void go(int &a,int b)
    {
        v.push({&a,a});
        return void(a = b);
    }
    void U(int a,int b)
    {
        a = get(a);b = get(b);
        if (a == b) return;
        if (sz[a] > sz[b])
            swap(a,b);
        go(f[a],b);
        go(sz[b],sz[a] + sz[b]);
    }
    void Restore(int Size)
    {
        while (v.size() > Size)
        {
            *v.top().fi = v.top().se;
            v.pop();
        }
    }
};
template < class T >
class Fenwick
{
    public:
    T * t;
    function < T(T,T) > comb;
    int n;
    public:
    void init(int N,T v,function < T(T,T) > cc)
    {
        n = N;
        t = new T[n + 5];
        for (int i = 0;i < n + 5;++i)
            t[i] = v;
        comb = cc;
    }
    T query(int i)
    {
        int ans = t[i];
        for (i -= i&(-i);i;i -= i&(-i))
            ans = comb(ans,t[i]);
        return ans;
    }
    void update(int i,T v)
    {
        for (;i <= n;i += i&(-i))
            t[i] = comb(t[i],v);
    }
};
int main(void)
{
    freopen("disjoint.in","r",stdin);
    freopen("disjoint.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    DSU ds;
    ds.init(n);
    while (m --)
    {
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if (op == 1)
            ds.U(a,b);
        else
            printf(ds.get(a) == ds.get(b) ? "DA\n":"NU\n");
    }
    return 0;
}