Untitled

 avatar
unknown
plain_text
2 years ago
1.0 kB
6
Indexable
#include <iostream>
using namespace std;
int n,m;
int kq;
int duongdi[21][21];
int visit[21];
int sum;
int dem[21];
void backtrack(int st){
	if(visit[st] > 2) return;
	if(visit[1] == 2 ){
		if(visit[2] == 1){
			if(sum < kq) kq = sum;
			return;
		}
		return;
	}
	for(int i = 0; i < dem[st]; i++){
		if(visit[duongdi[st][i]] < 2){
			visit[duongdi[st][i]]++;
			if(visit[duongdi[st][i]] == 1) sum++;
			backtrack(duongdi[st][i]);
			visit[duongdi[st][i]]--;
			if(visit[duongdi[st][i]] == 0) sum--;
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n >> m;
		for(int i = 1; i<= n; i++){
			visit[i] = 0;
			dem[i] = 0;
		}
		visit[1] = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				duongdi[i][j] = 0;
			}
		}
		for(int i = 0; i < m; i++){
			int x, y;
			cin >> x;
			cin >> y;
			duongdi[x][dem[x]] = y;
			dem[x]++;
		}
		kq = 1000;
		sum = 1;
		backtrack(1);
		cout << kq << endl;
	}
	return 0;
}
Editor is loading...