「CodeForces 402E」Strictly Positive Matrix

发表于 |
字数统计: 278 | 阅读时长 ≈ 1

给你一个$n*n$大小的矩阵，问你是否有一个正整数$k$使得这个矩阵的$k$次幂均为正数。

未完，贴代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct edge{
    ll to,prev;
};
edge ed[5000001];
ll tot,num,dist,top,cnt,nc;
ll last[5000001],dfn[5000001],low[5000001],ins[5000001],belong[5000001],size[5000001];
stack<ll>st;
inline void addEdge(ll from,ll to)
{
    ed[++tot].to=to;
    ed[tot].prev=last[from];
    last[from]=tot;
}
inline void tarjan(ll node)
{
    dfn[node]=low[node]=++num;
    st.push(node),ins[node]=1;
    ll flag=0,to;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        to=ed[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[node]=min(low[node],low[to]);
        }
        else
        {
            if(ins[to])
            {
                low[node]=min(low[node],dfn[to]);
            }
        }
    }
    if(dfn[node]==low[node])
    {
        cnt++;
        ll nd;
        do
        {
            nd=st.top(),st.pop();
            ins[nd]=0;
            belong[nd]=cnt;
            size[cnt]++;
        }
        while(node!=nd);
    }
}
int main()
{
    scanf("%d",&nc);
    for(register int i=0;i<nc;i++)
    {
    	for(register int j=0;j<nc;j++)
    	{
    		scanf("%d",&dist);
    		if(dist)
    		{
    			addEdge(i+1,j+1); 
            }
        }
    }
    for(register int i=1;i<=nc;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    cnt==1?printf("YES\n"):printf("NO\n");
}