QHROAD – spoj

Đề bài:

Thuật toán:

  • Kruskal những đoạn đường không bị phá.
  • Duyệt các truy vấn từ Q về 1. Nếu join thì giảm số tplt

Code:

#include <bits/stdc++.h>
using namespace std;
#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 pb push_back
#define mp make_pair
#define fi first
#define se second+++
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E5+3;
const ll oo = 1e18+3;
 
struct  edge {
	int u,v;
} e[MAXN];
int n, m, q, pa[MAXN], u , v, x, a[MAXN], tplt, ans[MAXN];
bool dt[MAXN];
 
int find(int u) {
	if (pa[u]!=u) pa[u] = find(pa[u]);
	return pa[u];
}
 
bool join(int u, int v) {
	int i = find(u);
	int j = find(v);
	if (i==j) return 0;
	else
	pa[i] = j;
	return 1;
}
 
int main() {
	cin >> n >> m >> q;
	FOR(i,1,m) {
		cin >> e[i].u >> e[i].v;
	}
	FOR(i,1,q) {
		cin >> x;
		dt[x] = 1;
		a[i] = x;
	}
	tplt = n;
	FOR(i,1,n) pa[i] = i;
	FOR(i,1,m)
	if (!dt[i]) {
		if (join(e[i].u,e[i].v)) tplt--;
	}
	FORD(i,q,1) {
		ans[i] = tplt;
		int id = a[i];
		if (join(e[id].u,e[id].v)) tplt--;
	}
	FOR(i,1,q) cout << ans[i] << endl;
   	return 0;
}
Khuyên dùng

 

Speak Your Mind

*