codeforces CF402E Strictly Positive Matrix Tarjan强连通分量

博客迁移计划7

$ \rightarrow $ 戳我进CF原题

E. Strictly Positive Matrix

---

time limit per test: 1 second memory limit per test: 256 megabytes input: standard input output: standard output

---

　
You have matrix $ a $ of size $ n \times n $ .
Let's number the rows of the matrix from $ 1 $ to $ n $ from top to bottom,
let's number the columns from $ 1 $ to $ n $ from left to right.
Let's use $ a_{ij} $ to represent the element on the intersection of the $ i $-th row and the $ j $-th column.
　
Matrix $ a $ meets the following two conditions:
　

• for any numbers $ i,j(1 \le i,j \le n) $ the following inequality holds: $ a_{ij} \ge 0 $ ;
• $ \sum^n_{i=1} a_{ij} > 0 $
  　
  Matrix $ b $ is strictly positive, if for any numbers $ i,j(1 \le i,j \le n) $ the inequality $ b_{ij} > 0 $ holds.
  You task is to determine if there is such integer $ k\ge 1 $ , that matrix $ a^k $ is strictly positive.

　

Input

The first line contains integer $ n (2 \le n \le 2000) $ — the number of rows and columns in matrix $ a $ .
　
The next $ n $ lines contain the description of the rows of matrix $ a $ .
The $ i $ -th line contains $ n $ non-negative integers $ a_{i1},a_{i2},\dots,a_{in} (0 \le a_{ij} \le 50 ) $ .
It is guaranteed that $ \sum^n_{i=1}a{ii} > 0 $ .
　

Output

If there is a positive integer $ k \le 1 $ , such that matrix $ a^k $ is strictly positive, print "YES" (without the quotes).
Otherwise, print "NO" (without the quotes).
　

Examples

input1

 2
 1 0
 0 1

output1

NO

---

input2

 5
 4 5 6 1 2
 1 2 3 4 5
 6 4 1 2 4
 1 1 1 1 1
 4 4 4 4 4

output2

YES

　

题目大意

• 给定一个 $ n*n $ 的矩阵 $ A $ ，每个元素都非负

• 判断是否存在一个整数 $ k $ 使得 $ A^k $ 的所有元素 $ >0 $

• $ n \le 2000 $
  　

题解

• 以 $ A $ 为有向图邻接矩阵 $ ( >0 $ 有边， $ = 0 $ 无边 ）

• 有邻接矩阵次幂的意义可知

• 判断是否为强连通图即可
  　

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
#define maxn 2005
vector<int>e[maxn];
stack<int>s;
int dfn[maxn],low[maxn],tim,scc;
bool vis[maxn];
void tarjan(int u){
	dfn[u]=low[u]=++tim; vis[u]=1; s.push(u);
	for(int v,i=0;i<e[u].size();++i)
		if(!dfn[v=e[u][i]]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(vis[v])
			low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u]){
		++scc;
		do{
			u=s.top(); s.pop(); vis[u]=0;
		}while(dfn[u]!=low[u]);
	}
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int a,j=1;j<=n;++j){
			scanf("%d",&a);
			if(a&&i!=j) e[i].push_back(j); 
		}
	for(int i=1;i<=n;++i) if(!dfn[i]&&scc<2) tarjan(i);
	if(scc==1) puts("YES");
	else puts("NO");
	return 0;
}