fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define	N 1000 			/* amounts of tree node */
  6.  
  7. /* 
  8.  * ===  FUNCTION  ======================================================================
  9.  *         Name:  allInSameSet
  10.  *  Description:  check all over the node in the same set 
  11.  * =====================================================================================
  12.  */
  13. 	bool
  14. allInSameSet ( int set[N], int index )
  15. {
  16. 	int i, setNum = 0;	
  17. 	for ( i = 1 ; i <= index ; i++ )        /* find the unique set */
  18. 		if ( 0 != set[i] ) {
  19. 			setNum = set[i];
  20. 			break;	
  21. 		}
  22. 	for ( int j = i; j <= index; j++ ) {
  23. 		if ( setNum != set[j] && 0 != set[j]) {
  24. 			return false;           /* there is one set not connected to tree */
  25. 		}
  26. 	}
  27. 	return true; 
  28. }		/* -----  end of function allInSameSet  ----- */
  29. /* 
  30.  * ===  FUNCTION  ======================================================================
  31.  *         Name:  combineSet
  32.  *  Description:  combine two sets to a parent's set 
  33.  * =====================================================================================
  34.  */
  35. 	void
  36. combineSet ( int set[N], int index, int par, int son)
  37. {
  38.  
  39. 	for ( int i = 1; i <= index; i++)
  40. 		if ( son == set[i]  && 0 != set[i] )
  41. 			set[i] = par;
  42. }		/* -----  end of function combineSet  ----- */
  43. /* * ===  FUNCTION  ======================================================================
  44.  *         Name:  main
  45.  *  Description:  set[node] == 0  means null. the number of set[node] means which set does
  46.  *  		  the node in .
  47.  *  		  divide nodes to sets, if node A point to node B then node A and B are
  48.  *  		  in the same set, Once there is intersection between sets, combine them.
  49.  * ===================================================================================== */ 
  50. 	int
  51. main ( int argc, char *argv[] )
  52. {
  53. 	int set[N];
  54. 	int a, b, sets = 1, max = -1, caseCount = 0;
  55. 	bool cycle = false;	
  56. 	while ( true ) {
  57. 		caseCount++;                    /* the number of cases */
  58. 		cycle = false;                  /* the flag of finding cycle in tree */
  59. 		memset(set, 0, sizeof(int)*N);  /* initial set */
  60. 		sets = 1;                       /* the first set */
  61. 		max = -1;                       /* upper bound of array */
  62. 		a = 0;
  63. 		b = 0;
  64. 		while ( 2 == scanf ( "%d %d", &a, &b )) {
  65.  
  66. 			if ( 0 >= a && 0 >= b ) /* input is (0, 0) or (-1, -1) */
  67. 				break;
  68.  
  69. 			if ( 0 >= a || 0 >= b )
  70. 			{
  71. 				cycle = true;   /* to use this flag to commit this graph is not tree */
  72. 			}
  73.  
  74. 			max = (a>b)?a:b;        /* find upper bound of array */
  75.  
  76. 			if ( (a == b) || (  (set[a] == set[b]) && ( 0 != set[a] && 0 != set[b]) ) ) {  
  77. 				cycle = true;   /* same input data or there is a edge between two nodes which location in same set */
  78. 			}
  79. 			else {
  80.  
  81. 				if ( 0 == set[a] && 0 == set[b] ) { /* new set */
  82. 					set[a] = sets;
  83. 					set[b] = sets++; 
  84. 				}
  85. 				else {
  86.  
  87. 					if ( 0 != set[a]   ) { /* because node a point to b, the element of set[b] are contained to set[a]*/
  88. 						combineSet(set, max, set[a], set[b]);
  89. 					}
  90. 					else {
  91. 						set[a] = set[b];
  92. 					}
  93. 				}
  94. 			}
  95. 		}                               /* end while */
  96.  
  97. 		if ( 0 > a && 0 > b ) {         /* input is end */
  98. 			break;
  99. 		}
  100. 		 /* :BUG:2012年06月11日 14時28分19秒:: if I input (0, 0) there maybe reason of Runtime error */
  101. 		if ( !cycle && allInSameSet(set, max) )
  102. 			printf ( "Case %d is a tree.\n", caseCount );
  103. 		else {
  104. 			printf ( "Case %d is not a tree.\n", caseCount );	
  105. 		}
  106. 	}                                       /* end while */
  107. 	return EXIT_SUCCESS;
  108. }				/* ----------  end of function main  ---------- */
Success #stdin #stdout 0.01s 2728KB
comments (?)
stdin 
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

0 0
1 2 0 0
1 2 1 3 4 5 0 0
1 1 0 0
1 2 2 1 0 0
1 2 1 2 0 0

1 2 2 3 3 1 4 5 0 0 

-1 -1
stdout 
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 8 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.
https://ideone.com/G5Blr
language:
C++ (gcc 8.3)
created:
11 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!