Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.4 kB
1
Indexable
Never
tiep code

#include <iostream>

using namespace std;
int T, N, M;
int x, y;
int arr[25][25];
int visited[25];

int ans;
int minA;
int flag;

void backtrack(int node){
	if(ans > minA){
		return;
	}
	if(node == 1 && flag == 1){
		if(ans < minA){
			minA = ans;
		}
	}
	for(int i = 1; i <= N; i++){
		if(arr[node][i] == 1){
			if(flag == 0){
				if(i == 2){
					if(visited[i] == 0){
						flag = 1;
						visited[i] = 2;
						ans++;
						backtrack(i);
						visited[i] = 0;
						ans--;
						flag = 0;
					}
				}else{
					if(visited[i] == 0){
						ans++;
						visited[i] = 1;
						backtrack(i);
						ans--;
						visited[i] = 0;
					}
				}
			}else{
				if(visited[i] != 2){
					if(visited[i] == 0){
						ans++;
						visited[i] = 2;
						backtrack(i);
						ans--;
						visited[i] = 0;
					}else{
						visited[i] = 2;
						backtrack(i);
						visited[i] = 1;
					}
				}
			}
		}
	}
}

int main(){
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M;
		for(int i = 0; i <= N; i++){
			for(int j = 0; j <= N; j++){
				arr[i][j] = 0;
			}
		}
		for(int i = 0; i < M; i++){
			cin >> x >> y;
			arr[x][y] = 1;
		}
		for(int i = 1; i <= N; i++){
			visited[i] = 0;
		}
		flag = 0;
		ans = 0;
		minA = 10000;
		backtrack(1);
		cout << minA << endl;
	}
	return 0;
}
Leave a Comment