Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
810 B
0
Indexable
Never
#include <iostream>
using namespace std;
int n,m;
int a[21][20];
int vis[21];
int dem[21];
int kq,sum;

void backtrack(int k){
	if(vis[2]!=1&&vis[k]==2) return;
	if(vis[1]!=2&&vis[k]==3) return;
	if(vis[1]>=2&&vis[2]==1){
		if(kq>sum) kq=sum;
		return;
	}
	if(sum>=kq) return;
	for(int i=0; i<dem[k]; i++){
		vis[a[k][i]]++;
		if(vis[a[k][i]]==1) sum++;
		backtrack(a[k][i]);
		vis[a[k][i]]--;
		if(vis[a[k][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=0; i<n; i++){
			dem[i]=0;
			vis[i]=0;
		}
		int x,y;
		for(int i=0; i<m; i++){
			cin>>x>>y;
			a[x][dem[x]]=y;
			dem[x]++;
		}
		kq=10000;
		sum=0;
		vis[1]=1;
		backtrack(1);
		cout<<kq+1<<endl;
	}
	return 0;
}
Leave a Comment