fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. int check[10];		//짝을 지었는지 확인
  7. int f[10][10];		//배열을 이용하여 친구끼리 묶기
  8. int num;		//학생 수
  9.  
  10. int solution(void)
  11. {
  12. 	int first = -1;
  13.  
  14. 	for (int i = 0; i < num; i++)				//가장 빠른 학생 찾기
  15. 	{
  16. 		if (!check[i])
  17. 		{
  18. 			first = i;
  19. 			break;
  20. 		}
  21. 	}
  22.  
  23. 	if (first == -1) return 1;				//학생의 짝을 다 찾았으면 1로 반환
  24.  
  25. 	int result = 0;
  26.  
  27. 	for (int i = first + 1; i < num; i++)
  28. 	{
  29. 		if (!check[i] && f[first][i])
  30. 		{
  31. 			check[first] = check[i] = 1;		//짝이 정해짐
  32. 			result += solution();
  33. 			check[first] = check[i] = 0;		// 다른 경우의 수를 찾기 위해
  34. 		}
  35. 	}
  36. 	return result;
  37. }
  38.  
  39. int main(void)
  40. {
  41. 	int test_case;
  42.  
  43. 	cin >> test_case;
  44.  
  45. 	while (test_case--)
  46. 	{
  47. 		int pair;
  48. 		cin >> num >> pair;				//num: 학생 수, pair: 친구 쌍의 수
  49.  
  50. 		memset(f, 0, sizeof(f));
  51. 		memset(check, 0, sizeof(check));
  52.  
  53. 		while (pair--)
  54. 		{
  55. 			int x, y;
  56.  
  57. 			cin >> x >> y;				//x: 친구1, y: 친구2
  58. 			f[x][y] = f[y][x] = 1;
  59. 		}
  60. 		cout << solution() << endl;
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
3 
2 1 
0 1 
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
stdout
copy 
1
3
4
https://ideone.com/wHOyS1
language:
C++ (gcc 8.3)
created:
4 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!