CSU1612Destroy Tunnels（强连通）传递闭包

原来早忘记了离散里含有这么一个叫传递闭包的东西

矩阵A的闭包B = A U A^2 U A^3 U ...

所以这里直接如果A[i][j]！= 0，建边i->j跑一遍强连通，看是不是只有一个强连通分量，>=2说明不能所有点都!=0输出exists

否则说明所有i->j(i!=j)都有B[i][j]！= 0输出not exists

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 #define dec(i, a, b) for(int i = a; i >= b; i --)
26  
27 template<class T> T CMP_MIN(T a, T b) { return a < b; }
28 template<class T> T CMP_MAX(T a, T b) { return a > b; }
29 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
30 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
31 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
33  
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN = 11000;
37 const int MAXM = 1100;
38 const double eps = 1e-4;
39 LL MOD = 1000000007;
40  
41 vector<int> G[MAXN];
42 int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt;
43 stack<int>S;
44  
45 void dfs(int u)
46 {
47     pre[u] = lowlink[u] = ++dfs_clock;
48     S.push(u);
49     int si = G[u].size();
50     for(int i = 0; i < si; i ++)
51     {
52         int v = G[u][i];
53         if(!pre[v]) {
54             dfs(v);
55             lowlink[u] = min(lowlink[u], lowlink[v]);
56         }
57         else if(!sccno[v]) {
58             lowlink[u] = min(lowlink[u], pre[v]);
59         }
60     }
61     if(lowlink[u] == pre[u]) {
62         scc_cnt++;
63         for(;;) {
64             int x = S.top(); S.pop();
65             sccno[x] = scc_cnt;
66             if(x == u) break;
67         }
68     }
69 }
70  
71  
72 void find_scc(int n)
73 {
74     dfs_clock = scc_cnt = 0;
75     mem0(sccno); mem0(pre);
76     for(int i = 0; i < n; i ++ )
77         if(!pre[i]) dfs(i);
78 }
79  
80 int t, n, x;
81  
82 int main()
83 {
84     while(~scanf("%d", &t)) while(t--) {
85         scanf("%d", &n);
86         rep (i, 0, n) G[i].clear();
87         rep (i, 0, n - 1) rep (j, 0, n - 1) {
88             scanf("%d", &x);
89             if(x) G[i].push_back(j);
90         }
91         find_scc(n);
92         puts(scc_cnt == 1 ? "not exists" : "exists");
93     }
94     return 0;
95 }
96

View Code