fork download
copy 
  1. #define gc() (*_pinp?*_pinp++:(_inp[fread(_pinp=_inp, 1, 4096, stdin)]='\0', *_pinp++))
  2. char _inp[4097], *_pinp=_inp, _; bool _ssign;
  3. #define nextInt(x) do{while((x=gc())<'-'); _ssign=x=='-'; if(_ssign) while((x=gc())<'0'); for(x-='0'; '0'<=(_=gc()); x=(x<<3)+(x<<1)+_-'0'); x=_ssign?-x:x;}while(0)
  4. #include <cstdio>
  5. #include <vector>
  6. using namespace std;
  7. int N, M;
  8. int p[100001], r[100001]; // parent, rank
  9. int size[150];
  10. void MAKE_SET(int x) {
  11. 	p[x]=x;
  12. 	r[x]=0;
  13. 	size[x]=1;
  14. }
  15. int FIND_SET(int x) {
  16. 	if (p[x]!=x)
  17. 		p[x]=FIND_SET(p[x]);
  18. 	return p[x];
  19. }
  20. void UNION(int x, int y) {
  21. 	int xr=FIND_SET(x);
  22. 	int yr=FIND_SET(y);
  23. 	if (xr==yr) return;
  24. 	if (r[xr]<r[yr]) {
  25. 		p[xr]=yr;
  26. 		size[yr]+=size[xr];
  27. 	} else if (r[xr]>r[yr]) {
  28. 		p[yr]=xr;
  29. 		size[xr]+=size[yr];
  30. 	} else {
  31. 		p[yr]=xr;
  32. 		r[xr]++;
  33. 		size[xr]+=size[yr];
  34. 	}
  35. }
  36. vector<int> a;
  37. int main() {
  38.     nextInt(N);
  39.     nextInt(M);
  40. 	for (int i=0; i<N; i++)
  41. 		MAKE_SET(i);
  42. 	for (int i=0; i<M; i++) {
  43. 		int u, v;
  44. 		nextInt(u);
  45. 		nextInt(v);
  46. 		if (FIND_SET(u)!=FIND_SET(v)) {
  47. 			a.push_back(i+1);
  48. 			UNION(u, v);
  49. 		}
  50. 	}
  51. 	   printf("%d\n", size[FIND_SET(6)]);
  52. 	int p=FIND_SET(0);
  53. 	for (int i=0; i<N; i++) {
  54. 		if (p!=FIND_SET(i)) {printf("Disconnected Graph\n"); return 0;}
  55. 	}
  56. 	for (int i=0; i<a.size(); i++)
  57. 	    printf("%i\n", a[i]);
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 16024KB
comments (?)
stdin
copy 
100 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
5 80
2 35
stdout
copy 
10
Disconnected Graph
https://ideone.com/ZHJKKX
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!