Untitled
unknown
plain_text
a year ago
1.0 kB
1
Indexable
Never
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> const int oo = 9999999; using namespace std; int a[25][25], n, m, cx[25], x[25]; int res; void dfs(int u) { cx[u] = 0; for (int v = 1; v <= n; v++) if (x[v] && cx[v] && a[u][v]) dfs(v); } void Update() { for (int i = 1; i <= n; i++) cx[i] = 1; dfs(1); if (cx[2]) return; for (int i = 1; i <= n; i++) cx[i] = 1; dfs(2); if (cx[1]) return; int d = 0; for (int i = 1; i <= n; i++) d += x[i]; res = min(res, d); } void Try(int i) { for (int j = 0; j < 2; j++) { x[i] = j; if (i == n) Update(); else Try(i + 1); } } main() { // freopen("in.txt", "r", stdin); int test; cin >> test; while (test--) { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = 0; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; a[x][y] = 1; } res = oo; x[1] = 1; x[2] = 1; Try(3); cout << res << endl; } }