思路:纯纯阅读理解题,它这个去电影院不是沿着道路走的,也就是不需要按照图的顺序访问,是直接挑选一个
s
c
c
scc
scc去访问 那问题就很好解决了,对于一个强联通块,必须访问他们的最少的点权的点,设为
n
u
m
[
x
]
num[x]
num[x]. 方案数目就是
∏
n
u
m
[
x
]
\prod num[x]
∏num[x] 对了,它是方案数取模,其他不取模,注意
/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int dfn[maxn],low[maxn],dfs_clock=0;int scc[maxn],scc_cnt;
stack S;
int mn[maxn],num[maxn];int a[maxn];
void dfs(int u){
low[u] = dfn[u] = ++dfs_clock;
S.push(u);
for(auto v : G[u]){
if(!dfn[v]){
dfs(v);
low[u] = min(low[u],low[v]);
}
else if(!scc[v]) low[u] = min(low[u],dfn[v]);//不是cross_edge而是back_edge的情况更新
}
if(low[u]==dfn[u]){
scc_cnt++;
while(true){
int x=S.top();S.pop();
if(a[x]>n;
for(int i=1;i>a[i];mn[i] = INF;
}
int m;cin>>m;
for(int i=1;i>u>>v;
G[u].pb(v);
}
for(int i=1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?