题意 ： 一个有向图，如果从0点出发到达某一点必须经过某些点 题目就是求出这些点。
?
点数不多 可以删点然后dfs搜索，之前能搜到的点 但是删了该点之后搜不到了 那么这个删点就是从起始点搜不到的必经之路。
#include #include #include #include #include #include #include #include #include #include #include #define lson o<<1,l,m #define rson o<<1|1,m+1,r #define mem(a) memset(a,0,sizeof(a)) typedef long long ll; const int N = 105; const int M = 10005; const ll mod = 1000000009; using namespace std; int n, T; int g[N][N], a[N][N]; int v1[N], v2[N]; int ans[N][N]; char out[N*3][N*3]; void dfs(int u) { if(v1[u]) return; v1[u] = 1; for(int i = 1; i <= n; i++) { if(g[u][i] && v1[i] == 0) dfs(i); } } void del(int u) { mem(g[u]); } void rec(int u) { memcpy(g[u], a[u], sizeof(a[u])); } void solve(int u) { mem(v1); dfs(1); for(int i = 1; i <= n; i++) { if(v1[i] == 0 && v2[i] == 1) { ans[u][i] = 1; } } } int main() { // freopen(in.txt, r, stdin); cin >> T; int ca = 1; while(T--) { cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf(%d, &g[i][j]); a[i][j] = g[i][j]; } } mem(v1); dfs(1); mem(ans); for(int i = 1; i <= n; ++i) if(v1[i]) { ans[1][i] = 1; ans[i][i] = 1; } memcpy(v2, v1, sizeof(v1)); for(int i = 2; i <= n; i++) { del(i); solve(i); rec(i); } mem(out); for(int i = 1; i <= n+n+1; i++) { if(i & 1) { out[i][1] = out[i][n+n+1] = '+'; for(int j = 2; j <= n+n; j++) { out[i][j] = '-'; } } else { for(int j = 1; j <= n+n+1; j++) { if(j & 1) { out[i][j] = '|'; } else { if(ans[i/2][j/2]) { out[i][j] = 'Y'; } else out[i][j] = 'N'; } } } } printf(Case %d: , ca++); for(int i = 1; i <= n+n+1; i++) { for(int j = 1; j <= n+n+1; j++) { printf(%c, out[i][j]); } puts(); } // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) { // printf(%d , ans[i][j]); // } // puts(); // }puts(); } return 0; }