fork download
copy 
  1. /*
  2. ID: 1436
  3. Name: Is it a tree?
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <math.h>
  8. #include <string.h>
  9. #include <stdlib.h>
  10.  
  11. struct Edge
  12. {
  13. 	int d;
  14. 	int s;
  15. };
  16. struct Graph
  17. {
  18. 	int N;
  19. 	int M;
  20. 	struct Edge* edge;
  21. };
  22.  
  23. struct Graph* createGraph(int N, int M)
  24. {
  25. 	struct Graph* g = (struct Graph*) malloc(sizeof(struct Graph));
  26. 	g -> M = M;
  27. 	g -> N = N;
  28. 	g -> edge = (struct Edge*) malloc (sizeof(struct Edge));
  29.  
  30. 	return g;
  31. }
  32. int findP(int p[], int v)
  33. {
  34. 	if (p[v] == -1)
  35. 		return v;
  36. 	return findP(p, p[v]);
  37. }
  38. void Union(int p[], int x, int y) 
  39. {
  40. 	int xS = findP(p, x);
  41. 	int yS = findP(p, y);
  42.  
  43. 	p[xS] = yS;
  44. }
  45. int cycle(struct Graph* g)
  46. {	
  47. 	int *par = (int*) malloc(((g -> N)+1) * sizeof(int));
  48. 	memset(par, -1, ((g -> N)+1) * sizeof(int));
  49.  
  50. 	for (int i=0; i<g -> M; i++) {
  51. 		int x = findP(par, g->edge[i].s);
  52. 		int y = findP(par, g->edge[i].d);
  53.  
  54. 		if (x == y)
  55. 			return 1;
  56. 		Union(par, x, y);
  57. 	}
  58. 	return 0;
  59. }
  60. int main ()
  61. {
  62. 	int N, M;
  63. 	scanf("%d %d", &N, &M);
  64.  
  65. 	struct Graph* g = createGraph(N, M);
  66.  
  67. 	for (int i=0; i<M; i++) {
  68. 		int a, b;
  69. 		scanf("%d %d", &a, &b);
  70.  
  71. 		if (a != b) {
  72. 			g -> edge[i].s = a;
  73. 			g -> edge[i].d = b;		 
  74. 		}
  75. 	}
  76. 	if (M != N-1) {
  77. 		printf("NO\n");
  78. 		return 0;
  79. 	}
  80. 	if (cycle(g))
  81. 		printf("NO\n");
  82. 	else
  83. 		printf("YES\n");
  84. }
Success #stdin #stdout 0.79s 9416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/q7vIyT
language:
C (clang 8.0)
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!