【Codefoeces 402E】一个有趣的转化

1.​​题目链接​​。题目大意：给定一个矩阵原来矩阵里面所有的数据都是非负数，让你确定是不是存在一个k使得这个矩阵的k次幂之后，矩阵的每一个数据都是正数。

2.我们可以把这个矩阵看成一个有向图的邻接矩阵，我们知道，在有向图的邻接矩阵里面，它k次幂之后，每个元素的值是具有十分重要的意义的。matrix[a][b]-->matrix^k[a][b].就是代表从a到b走了k步有多少种方案数。这个之前提到过。其实就是在说这个图是不是强连通的。如果图是强连通的，任意两个点都是可以互相到达的，那么一定是存在一个k使得k次之后，所有的元素都不为0.这个k是任意两点互相达到的步数的最小公倍数。当然了题目没有让我们求k，只是判断图是不是强连通，直接跑一遍tarjan算法统计图中强连通的数量即可。

#include<bits/stdc++.h>
#include <iostream>
#pragma warning(disable:4996)
using namespace std;
const int N = 2e3 + 10;
int gra[N][N];
int sta[N], vis[N], low[N], dfn[N], top;
void tarbfs(int k, int cnt, int &num, int n)
{

vis[k] = 1;
low[k] = cnt;
dfn[k] = cnt;
for (int j = n; j > 0; j--)
{
if (gra[k][j] > 0 && vis[j] == 0) tarbfs(j, ++cnt, num, n);
if (gra[k][j] > 0 && vis[j] == 1) low[k] = min(low[k], low[j]);
}
if (dfn[k] == low[k])
{
++num;
}
}
int tarjan(int n) {
int num = 0, cnt = 1;
top = 0;
memset(vis, 0, sizeof(vis));
memset(low, 0, sizeof(low));
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) tarbfs(i, cnt, num, n);
}
return num;
}
int main()
{
int n, a;
while (cin >> n)
{
memset(gra, 0, sizeof(gra));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
scanf("%d", &a);
if (a > 0) gra[i][j] = 1;
}
}
int num = tarjan(n);
if (num == 1) puts("YES");
else puts("NO");
}
return 0;
}