程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 11902 （有向圖的關節點）

UVA - 11902 （有向圖的關節點）

編輯：C++入門知識

UVA - 11902 （有向圖的關節點）

題意：一個有向圖，如果從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;
}