fork download
copy 
  1. #include <stdio.h>;
  2. #include <stdlib.h>;
  3. int Ind[300001];
  4. int size[300001];
  5. int find(int p) {
  6. 	while (p != Ind[p])
  7. 		p = Ind[p];
  8. 	return p;
  9. }
  10. void Union(int p, int q) {
  11. 	int r1 = find(p);
  12. 	int r2 = find(q);
  13. 	if (r1 == r2) return;
  14. 	if (size[r1]<size[r2])
  15. 	{
  16. 		Ind[r1] = r2;
  17. 		size[r2] += size[r1];
  18. 	}
  19. 	else
  20. 	{
  21. 		Ind[r2] = r1;
  22. 		size[r1] += size[r2];
  23. 	}
  24. }
  25.  
  26. void main() {
  27. 	int N, a, b;
  28. 	scanf("%d", &N);
  29. 	for (int i = 1; i <= N; i++)
  30. 	{
  31. 		Ind[i] = i;
  32. 		size[i] = 1;
  33. 	}
  34. 	if (N == 2)
  35. 	{
  36. 		printf("1 2");
  37. 	}
  38. 	else {
  39. 		for (int i = 0; i < N-2; i++)
  40. 		{
  41. 			scanf("%d %d", &a, &b);
  42. 			Union(a, b);
  43. 		}
  44. 		int root = find(1);
  45. 		for (int i = 2; i <= N; i++)
  46. 		{
  47. 			if (find(i) != root)
  48. 			{
  49. 				printf("%d %d", root, i);
  50. 				break;
  51. 			}
  52. 		}
  53. 	}
  54. 	exit(0);
  55. }
  56.  
  57.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
7
2 1
2 3
3 4
5 6
5 4
stdout
copy 
2 7
https://ideone.com/29fKmQ
language:
C (gcc 8.3)
created:
12 days 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!