rt,第十二个点的答案在小数点第五位偏小,答案似乎有很多个孤立点的样子,不知道为什么会算错
#include<bits/stdc++.h>//smaller
using namespace std;
const int N=2e5+10;
int head[N],Head[N],tto,tot,n,m;
struct E {
int nxt,to;
} e[N<<1],edge[N<<1];
typedef long double db;
inline void link(int x,int y,int w=0) {
if(w) {
edge[++tto]=(E) {
Head[x],y
};
Head[x]=tto;
return;
}
e[++tot]=(E) {
head[x],y
};
head[x]=tot;
}
int low[N],dfn[N],st[N],top,vis[N],tg[N];
int dfstime,inst[N],col[N],node,siz[N];
inline int Min(int x,int y) {
return x<y?x:y;
}
void tarjan(int x) {
low[x]=dfn[x]=++dfstime;
st[++top]=x;
inst[x]=1;
for(int i=head[x]; i; i=e[i].nxt) {
int j=e[i].to;
if(!dfn[j]) {
tarjan(j);
low[x]=Min(low[x],low[j]);
} else if(inst[j])low[x]=Min(low[x],dfn[j]);
}
if(dfn[x]==low[x]) {
++node;
col[node]=node;
int y=-1;
while(y=st[top--]) {
col[y]=node;
siz[node]++;
inst[y]=0;
if(x==y)return;
}
}
}
struct EE {
int u,v;
} edges[N];
int cnt_eg,in[N],V[N];
map<int,map<int,int> >mp;
int main() {
freopen("in.txt","r",stdin);
freopen("My.out","w",stdout);
scanf("%d%d",&n,&m);
node=n;
for(int i=1; i<=node; ++i)siz[i]=1;
for(int i=1; i<=m; ++i) {
int u,v;
scanf("%d%d",&u,&v);
swap(u,v);
link(v,u);
edges[++cnt_eg]=(EE) {
v,u
};
}
for(int i=1; i<=n; ++i)if(!dfn[i])top=0,tarjan(i);
for(int i=1; i<=cnt_eg; ++i) {
int u=edges[i].u;
int v=edges[i].v;
u=col[u];
v=col[v];
tg[u]=1;
tg[v]=1;
if(u==v)continue;
if(mp[u][v])continue;
mp[u][v]=1;
vis[u]=1;
vis[v]=1;
link(u,v,1);
in[v]++;
}
int cnt=0;
int Fg=-1;
for(int i=n+1; i<=node; ++i) {
if(!in[i])cnt++;
if(in[i]||siz[i]>1)continue;
if(Fg==-1) {
int fg=1;
for(int g=Head[i]; g; g=edge[g].nxt) {
int v=edge[g].to;
if(in[v]<=1) {
fg=0;
break;
}
}
if(!Head[i])fg=1;
if(fg) {
Fg=1;
cnt--;
}
}
}
printf("%.6lf\n",(double)(n-cnt)/n);
return 0;
}