题目
http://uva.onlinejudge.org/external/119/11902.html
题目概述：
结点X “dominates” 另一个结点Y，表示X一定经过Y，且当X结点被删掉时，从初始结点不能到达Y。由此可知，每个结点都“dominates”它本身。
解题方法：
通过DFS（深度优先搜索），去掉一个结点，即可用VISITED表示这个结点已经被遍历过。另外，设一个数组来存储结点间dominate的关系。因为$T<=100$, $0 < N < 100$,所以可以用$O(N^2)$的时间复杂度以及AdjMat的图存储方式。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <vector>
#define UNVISITED 0
#define VISITED 1
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
int AdjMat[105][105];
bool res[105][105];
vi dfs_num;
int T, V;
void (int u){
dfs_num[u] = VISITED;
for(int i = 0;i < V;i++){
if(!dfs_num[i] && AdjMat[u][i])
dfs(i);
}
}
void printLineBreak(){
printf("+");
for(int j = 0;j < 2 * V - 1;j++) printf("-");
printf("+n");
}
int main(){
scanf("%d", &T);
for(int ca=1; ca <= T;ca++){
scanf("%d", &V);
fill(AdjMat[0], AdjMat[0]+105*105, 0);
fill(res[0], res[0]+105*105, false);
dfs_num.assign(V, UNVISITED);
for(int i = 0;i < V;i++)
for(int j = 0;j < V;j++)
scanf("%d", &AdjMat[i][j]);
bool dominates[105][105];
fill(dominates[0], dominates[0]+105*105, false);
dominates[0][0] = true;
for(int removed_node=1;removed_node<V;removed_node++){
dominates[0][removed_node] = true;
fill(dfs_num.begin(), dfs_num.end(), 0);
dfs_num[removed_node] = true;
dfs(0);
for(int i = 0;i < V;i++)
if(!dfs_num[i])
dominates[removed_node][i] = true;
dominates[removed_node][removed_node] = true;
}
fill(dfs_num.begin(), dfs_num.end(), 0);
dfs(0);
printf("Case %d:n", ca);
printLineBreak();
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf(dominates[i][j] && dfs_num[j] ? "|Y" : "|N");
}
printf("|n");
printLineBreak();
}
}
return 0;
}
|
近期评论