HDU 5961：传递（暴搜）

http://acm.hdu.edu.cn/showproblem.php?pid=5961

题意：中文题意。给出两个图，判断这个两个图是否都是传递的。注意一下传递的定义要看清，一开始没看清连样例都看不懂。

思路：点数很少，有了异或那题的暴力之后，这题继续试着爆搜了一下，也能过。主要存两个图，然后dfs的时候传入当前点的上一个点fa，如果 fa 和下一个点 v 之间没有边相连，那么就不满足条件了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <string>
  7 #include <iostream>
  8 #include <stack>
  9 #include <map>
 10 #include <queue>
 11 using namespace std;
 12 #define N 2050
 13 #define INF 0x3f3f3f3f
 14 struct node
 15 {
 16     int v, nxt;
 17 }e1[N*N], e2[N*N];
 18 int head1[N], head2[N], tot1, tot2;
 19 int m1[N][N];
 20 int m2[N][N];
 21 bool vis[N], f;
 22 char maze[N][N];
 23 
 24 void add1(int u, int v)
 25 {
 26     e1[tot1].v = v; e1[tot1].nxt = head1[u]; head1[u] = tot1++;
 27 }
 28 
 29 void add2(int u, int v)
 30 {
 31     e2[tot2].v = v; e2[tot2].nxt = head2[u]; head2[u] = tot2++;
 32 }
 33 
 34 void dfs1(int u, int fa)
 35 {
 36     vis[u] = 1;
 37     for(int i = head1[u]; ~i; i = e1[i].nxt) {
 38         int v = e1[i].v;
 39         if(vis[v]) continue;
 40         vis[v] = 1;
 41 //        printf("dfs1 : %d, %d, %d
", fa, u, v);
 42         if(!m1[fa][v]) f = 0;
 43         dfs1(v, u);
 44     }
 45 }
 46 
 47 void dfs2(int u, int fa)
 48 {
 49     for(int i = head2[u]; ~i; i = e2[i].nxt) {
 50         int v = e2[i].v;
 51         if(vis[v]) continue;
 52         vis[v] = 1;
 53         if(!m2[fa][v]) f = 0;
 54         dfs2(v, u);
 55     }
 56 }
 57 
 58 int main()
 59 {
 60     int t;
 61     scanf("%d", &t);
 62     while(t--) {
 63         int n;
 64         scanf("%d", &n);
 65         for(int i = 0; i < n; i++) scanf("%s", maze[i]);
 66         memset(m1, 0, sizeof(m1));
 67         memset(m2, 0, sizeof(m2));
 68         memset(head1, -1, sizeof(head1));
 69         memset(head2, -1, sizeof(head2));
 70         tot1 = tot2 = 0;
 71         for(int i = 1; i <= n; i++) {
 72             for(int j = 1; j <= n; j++) {
 73                 if(maze[i-1][j-1] == '-') ;
 74                 else if(maze[i-1][j-1] == 'P') {
 75                     m1[i][j] = 1; add1(i, j);
 76                 } else {
 77                     m2[i][j] = 1; add2(i, j);
 78                 }
 79             }
 80         }
 81         f = 1;
 82         memset(vis, 0, sizeof(vis));
 83         for(int i = 1; i <= n && f; i++) {
 84             if(!vis[i]) {
 85                 vis[i] = 1;
 86                 dfs1(i, i);
 87             }
 88         }
 89         memset(vis, 0, sizeof(vis));
 90         for(int i = 1; i <= n && f; i++) {
 91             if(!vis[i]) {
 92                 vis[i] = 1;
 93                 dfs2(i, i);
 94             }
 95         }
 96         if(f) puts("T");
 97         else puts("N");
 98     }
 99     return 0;
100 }
101 
102 /*
103 1
104 4
105 -P-P
106 --PQ
107 P--Q
108 ----
109 */