书接上回
银狼在模拟宇宙中走了一遍最短路
突然发现,这里不只她所需要的奇物『赛博朋克精神』,还有很多稀奇古怪的奇物
她打算把每种奇物都归为同一类
比如:
『好玩的』,『不如原神的』,『正确的』,『没啥用的』....
这让她不禁想到了一种算法----------『Tarjan
』
这种名为塔尖(不管了就是这么读的,塔杨是啥)的算法通过以太编辑就可以做到上面的分类
"容易!"她心想
哼,黑塔的奇物保不住了,但是因为避免程序跑的太慢拿不到奇物,所以她只能在1s内完成这个操作,并且以太编辑虽然是高科技但是却无法存储很多信息,只有128MB的可用空间
于是....她几下就打出了下面的程序
点击查看银狼的SCC缩点
#include<bits/stdc++.h>
#define lC q<<1
#define rC q<<1|1
#define int long long
#define INF 0x66ccff0712
#define endl "\n"
#define maxm 0x66ccff
#define maxn 0x6cf
#define mid ((l+r)>>1)
#define void inline void
using namespace std;
inline int read(){
int s = 0,w = 1;char ch = getchar();
while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
return s*w;
}
struct HuaFengXiaYun{
int ver,Next,edge;
}tree[maxm];
struct LuoShuiTianYi{
int ver,Next,edge,dfn,low;
}t[maxm];
int head[maxm],out[maxm],tc,headc[maxm],n,m,tot,num,f,root,sta[maxm],top,cnt,ins[maxm],c[maxm];
bool cut[maxm];
vector<int>scc[maxm];
void add(int x,int y/*,int z*/){
t[++tot].ver=y;
// t[tot].edge=z;
t[tot].Next=head[x];
head[x]=tot;
}
void add_c(int x,int y){
tree[++tc].ver=y;
tree[tc].Next=headc[x];
headc[x]=tc;
}
void tarjan(int x){
t[x].dfn=t[x].low=++num;
sta[++top]=x;
ins[x]=1;
for(int i=head[x];i;i=t[i].Next){
if(!t[t[i].ver].dfn){
tarjan(t[i].ver);
t[x].low=min(t[x].low,t[t[i].ver].low);
}
else
t[x].low=min(t[x].low,t[t[i].ver].dfn);
}
if(t[x].dfn==t[x].low){
cnt++;
int y;
while(x!=y){
y=sta[top--],
ins[y]=0;
c[y]=cnt,
scc[cnt].push_back(y);
}
}
}
signed main(){
n=read(),m=read();
tot=1;
for(int i=1;i<=m;i++){
int x=read(),y=read()/*,z=read()*/;
if(x==y) continue;
add(x,y/*,z*/);
}
for(int i=1;i<=n;i++)
if(!t[i].dfn)
tarjan(i);
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=t[i].Next){
int y=t[i].ver;
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
}
}
for(int i=headc[1];i;i=tree[i].Next){
summ[i]++;
}
int abc=0,ans=0;
for(int i=1;i<=cnt;i++){
if(summ[i]==0)
abc++,
ans+=scc[i].size();
}
cout<<ans;
}
当她尝试运行这段代码时
她失败了
又来???
她仔细的查看编译信息....
...为什么
#define maxm 0x66ccff
.........
vector<int>scc[maxm];
好好好,这么玩是吧,600万的二维数组
银狼随手便修改完毕
....
又来?
90分...
难道是这组数据出锅了?
银狼仔细的审视错误
好好好
缩点之后怎么...还是用的缩点前的head访问
那怎么是90pts?
模拟宇宙的奇物种类太水了吧
(更新时间:下次出现若智错误)