Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int M = 1000100, N = 100100;

struct edge
{
    int x, y, z, id, q;

    bool operator < (edge u) const
    {
        return z < u.z;
    }
} a[M + 33 * 111];

int n, m, Q, s[33], query[33][111], cur[M], d[N];
edge q[33];

int get(int x)
{
    return x == d[x] ? x : d[x] = get(d[x]);
}

int solve(int numQuery, int s, int query[], edge q)
{
    for (int i = 0; i < s; i++) cur[query[i]] = numQuery;
    for (int i = 1; i <= n; i++) d[i] = i;

    int connected = 0, len = 1 << 30, lim = 1 << 30;
    for (int i = 1; i <= m; i++)
        if (a[i].q == numQuery || (!a[i].q && cur[a[i].id] != numQuery) && a[i].z <= len)
        {
            if (a[i].id == q.id) 
            {
                lim = a[i].z;
                break;
            }

            int x = get(a[i].x), y = get(a[i].y);
            if (x == y) continue;
            d[x] = y;
            if (get(q.x) == get(q.y) && !connected)
            {
                len = a[i].z;
                connected = 1;
            }
        }

    return len < lim;
}

int main()
{
    int test;
    cin >> test;
    while (test--)
    {
        cin >> n >> m >> Q;
        for (int i = 1; i <= m; i++) 
        {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
            a[i].id = i; 
            a[i].q = cur[i] = 0;
        }

        for (int i = 1; i <= Q; i++)
        {
            int k;
            scanf("%d%d", &k, s + i);
            q[i] = a[k];
            for (int j = 0; j < s[i]; j++) 
            {
                scanf("%d", query[i] + j);
                a[++m] = a[query[i][j]];
                scanf("%d", &a[m].z);
                a[m].q = i;
            }
        }

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

        for (int i = 1; i <= Q; i++) puts(solve(i, s[i], query[i], q[i])?"YES":"NO");
    }
}

Code mẫu của happyboy99x

#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const int N = 1e5, M = 1e6;
int edge[M][3], label[N], n, m, q;

void enter() {
    GN(n); GN(m); GN(q);
    for(int i = 0; i < m; ++i) {
        GN(edge[i][0]); GN(edge[i][1]); GN(edge[i][2]);
        --edge[i][0]; --edge[i][1];
    }
}

pair<int, int> e[M];

void prepare() {
    for(int i = 0; i < m; ++i) e[i] = make_pair(edge[i][2], i);
    sort(e, e + m);
}

int getSet(int u) {
    return label[u] < 0 ? u : label[u] = getSet(label[u]);
}

bool joinSet(int u, int v) {
    int x = getSet(u), y = getSet(v);
    if(x == y) return false;
    if(label[x] < label[y]) swap(x, y);
    label[y] += label[x];
    label[x] = y;
    return true;
}

bool changed[M];

const char * query() {
    int which; GN(which); --which;
    int limit = edge[which][2];
    int numChange; GN(numChange);
    vector<pair<int, int> > newEdge;
    for(int i = 0; i < numChange; ++i) {
        int id, newCost; GN(id); GN(newCost); --id;
        changed[id] = true;
        if(id == which) limit = newCost;
        newEdge.push_back(make_pair(newCost, id));
    }
    sort(newEdge.begin(), newEdge.end());
    int limOld = m, limNew = numChange;
    while(limOld > 0 && e[limOld - 1].first >= limit) --limOld;
    while(limNew > 0 && newEdge[limNew - 1].first >= limit) --limNew;
    fill_n(label, n, -1);
    int added = 0;
    for(int i = 0, j = 0; (i < limOld || j < limNew) && added < n - 1 && getSet(edge[which][0]) != getSet(edge[which][1]); ) {
        if(i < limOld && changed[e[i].second]) { ++i; continue; }
        if(i == limOld || (j < limNew && e[i].first > newEdge[j].first)) {
            if(joinSet(edge[newEdge[j].second][0], edge[newEdge[j].second][1])) ++added;
            ++j;
        } else {
            if(joinSet(edge[e[i].second][0], edge[e[i].second][1])) ++added;
            ++i;
        }
    }
    for(int i = 0; i < numChange; ++i) changed[newEdge[i].second] = false;
    if(added == n - 1) return "YES";
    return getSet(edge[which][0]) != getSet(edge[which][1]) ? "NO" : "YES";
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int test; GN(test);
    for(int i = 0; i < test; ++i) {
        enter();
        prepare();
        for(int i = 0; i < q; ++i) puts(query());
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<ii, int>
#define X first
#define Y second
const int N = 100005;
const int M = 2000006;
using namespace std;
vector<ii> a[N];
iii e[M];
int n, m, q, t;
bool visit[N], del[M];
int Q[N];
ii st[111];

void Enter() {
    scanf("%d %d %d\n", &n, &m, &q);
    int i, u, v, c;
    for(i=1; i<=n; i++) a[i].clear();
    for(i=1; i<=m; i++) {
        scanf("%d %d %d\n", &u, &v, &c);
        e[i] = iii(ii(u, v), c);
        a[u].push_back(ii(v, i));
        a[v].push_back(ii(u, i));
    }
}

bool Cycle(iii edge) {
    int s = edge.X.X, t = edge.X.Y;
    int l = 1, r = 1, i, u, v, pos;
    for(i = 1; i<=n; i++) visit[i] = false;
    Q[1] = s;
    visit[s] = true;
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i].X; pos = a[u][i].Y;
            if (!del[pos] && !visit[v] && e[pos].Y < edge.Y) {
                Q[++r] = v;
                visit[v] = true;
                if (v == t) return true;
            }
        }
    }
    return false;
}

void Answer() {
    int i, k, s, p, c;
    while (q--) {
        scanf("%d %d", &k, &s);
        for(i=1; i<=s; i++) {
            scanf("%d %d", &p, &c);
            st[i] = ii(p, e[p].Y);
            e[p].Y = c;
        }
        del[k] = true;
        if (Cycle(e[k])) printf("YES\n"); else printf("NO\n");
        del[k] = false;
        for(i=1; i<=s; i++) e[st[i].X].Y = st[i].Y;
    }
}

int main()
{
    scanf("%d\n", &t);
    while (t--) {
        Enter();
        Answer();
    }
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Van Hanh Pham - skyvn97 */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

class DisjointSet {
    private:
    vector<int> lab;

    int find(int x) {
        return lab[x] < 0 ? x : lab[x] = find(lab[x]);
    }

    public:
    DisjointSet(int n = 0) {
        lab.assign(n + 7, -1);
    }

    bool join(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x == y) return false;
        if (lab[x] > lab[y]) swap(x, y);
        lab[x] += lab[y];
        lab[y] = x;
        return true;
    }

    bool sameSet(int x, int y) {
        return find(x) == find(y);
    }
};

#define MAXV   100100
#define MAXE   1000100

const char YES[] = "YES";
const char NO[] = "NO";

#define STATIC   true
#define DYNAMIC   false
struct Edge {
    int u, v, c, newC;
    bool type;

    Edge() {
        u = v = c = newC = 0;
        type = STATIC;
    }

    void input(void) {
        scanf("%d%d%d", &u, &v, &c);
        newC = -1;
        type = STATIC;
    }

    int getCost(void) const {
        return type == DYNAMIC && newC > 0 ? newC : c;
    }

    bool operator < (const Edge &e) const {
        return c < e.c;
    }
};

Edge edges[MAXE];

struct Query {
    int askedEdge, askedValue, index;
    bool answer;
    vector<pair<int, int> > changes;

    Query() {
        askedEdge = askedValue = 0;
    }

    void input(int index) {
        this->index = index;

        scanf("%d", &askedEdge);
        askedValue = edges[askedEdge].c;

        changes.clear();

        int t; scanf("%d", &t);
        REP(love, t) {
            int id, c; scanf("%d%d", &id, &c);
            changes.push_back(make_pair(id, c));
            if (id == askedEdge) askedValue = c;
            edges[id].type = DYNAMIC;
        }
    }

    bool operator < (const Query &q) const {
        return askedValue < q.askedValue;
    }
};

int numNode, numEdge, numQuery;
Query queries[MAXV];

vector<int> staticEdges, dynamicEdges;

void loadGraph(void) {
    scanf("%d%d%d", &numNode, &numEdge, &numQuery);
    FOR(i, 1, numEdge) edges[i].input();
    FOR(i, 1, numQuery) queries[i].input(i);
    staticEdges.clear();
    dynamicEdges.clear();
}

bool compare(const int &x, const int &y) {
    return edges[x].c < edges[y].c;
}
bool compID(const Query &q1, const Query &q2) {
    return q1.index < q2.index;
}
void process(void) {
    sort(queries + 1, queries + numQuery + 1);
    FOR(i, 1, numEdge) {
        if (edges[i].type == STATIC) staticEdges.push_back(i);
        else dynamicEdges.push_back(i);
    }

    sort(ALL(staticEdges), compare);

    int j = 0;

    DisjointSet staticDSU(numNode);

    FOR(i, 1, numQuery) {
        while (j < staticEdges.size() && edges[staticEdges[j]].c < queries[i].askedValue) {
            int id = staticEdges[j++];
            staticDSU.join(edges[id].u, edges[id].v);
        }

        FORE(it, queries[i].changes) edges[it->fi].newC = it->se;

        DisjointSet dsu = staticDSU;
        FORE(it, dynamicEdges) if (edges[*it].getCost() < queries[i].askedValue)
            dsu.join(edges[*it].u, edges[*it].v);

        int asked = queries[i].askedEdge;
        queries[i].answer = dsu.sameSet(edges[asked].u, edges[asked].v);

        FORE(it, queries[i].changes) edges[it->fi].newC = -1;
    }

    sort(queries + 1, queries + numQuery + 1, compID);
    FOR(i, 1, numQuery) printf("%s\n", queries[i].answer ? YES : NO);
}

int main(void) {
    int t; scanf("%d", &t);
    REP(love, t) {
        loadGraph();
        process();
    }
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/