fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  4. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  5. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  6. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  7. #define ALL(v) (v).begin(),(v).end()
  8. #define pb push_back
  9. #define mp make_pair
  10. #define fi first
  11. #define se second+++
  12. #define SZ(x) ((int)(x).size())
  13. #define double db
  14. typedef long long ll;
  15. typedef pair<int,int> PII;
  16. const ll mod=1000000007;
  17. 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;}
  18. const int MAXN = 1E5+3;
  19. const ll oo = 1e18+3;
  20.  
  21. struct  edge {
  22. 	int u,v;
  23. } e[MAXN];
  24. int n, m, q, pa[MAXN], u , v, x, a[MAXN], tplt, ans[MAXN];
  25. bool dt[MAXN];
  26.  
  27. int find(int u) {
  28. 	if (pa[u]!=u) pa[u] = find(pa[u]);
  29. 	return pa[u];
  30. }
  31.  
  32. bool join(int u, int v) {
  33. 	int i = find(u);
  34. 	int j = find(v);
  35. 	if (i==j) return 0;
  36. 	else
  37. 	pa[i] = j;
  38. 	return 1;
  39. }
  40.  
  41. int main() {
  42. 	cin >> n >> m >> q;
  43. 	FOR(i,1,m) {
  44. 		cin >> e[i].u >> e[i].v;
  45. 	}
  46. 	FOR(i,1,q) {
  47. 		cin >> x;
  48. 		dt[x] = 1;
  49. 		a[i] = x;
  50. 	}
  51. 	tplt = n;
  52. 	FOR(i,1,n) pa[i] = i;
  53. 	FOR(i,1,m)
  54. 	if (!dt[i]) {
  55. 		if (join(e[i].u,e[i].v)) tplt--;
  56. 	}
  57. 	FORD(i,q,1) {
  58. 		ans[i] = tplt;
  59. 		int id = a[i];
  60. 		if (join(e[id].u,e[id].v)) tplt--;
  61. 	}
  62. 	FOR(i,1,q) cout << ans[i] << endl;
  63.    	return 0;
  64. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qG1hZ4
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!