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

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

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

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

#include#include #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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。