题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2438
数据生成器：http://paste.ubuntu.com/19584806/
PS:此题的随机数据不容易拍出错QAQ
来练习Tarjan的scc，然而此题细节比较多，被卡了好久QAQ
很明显，如果一个scc中知道了一个点，则其他点都可以安全推出
所以我们只需要搞出入度为零的scc有多少个即可
然而还有一个坑：
如果最后问得只剩一个单独的点了，这个点是不需要询问的
所以遇到这种单独的点，并且他连向的点的入度都不为一的话，ans -= 1
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int MAXN = 300000+9;
int n,m,to[MAXN],nxt[MAXN],head[MAXN];
int num[MAXN],lowlink[MAXN],in[MAXN],vout;
int scc_num[MAXN],scc_sz[MAXN],scc_cnt;
stack<int> sta;
inline void AddEdge(int u, int v){
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
}
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
void DFS(int w) {
static int tot = 0; sta.push(w);
num[w] = lowlink[w] = ++tot;
for (int i=head[w];i;i=nxt[i]) {
if (!num[to[i]]) DFS(to[i]), lowlink[w] = min(lowlink[w], lowlink[to[i]]);
else if (!scc_num[to[i]]) lowlink[w] = min(lowlink[w], lowlink[to[i]]);
}
if (lowlink[w] == num[w]) {
scc_cnt += 1;
while (true) {
int nw = sta.top(); sta.pop();
scc_num[nw] = scc_cnt;
scc_sz[scc_cnt]++;
if (nw == w) break;
}
}
}
int main(){
n = read(); m = read(); if (n==1) {printf("1.000000\n"); return 0;}
for (int i=1,u,v;i<=m;i++) u = read(), v = read(), AddEdge(u,v);
for (int i=1;i<=n;i++) if (!num[i]) DFS(i);
for (int i=1;i<=n;i++) for (int j=head[i];j;j=nxt[j])
if (scc_num[to[j]] != scc_num[i]) in[scc_num[to[j]]]++;
for (int i=1;i<=scc_cnt;i++) if (!in[i]) vout++;
for (int i=1,tag=0;i<=n;i++,tag=0) if (scc_sz[scc_num[i]] == 1 && !in[scc_num[i]]) {
for (int j=head[i];j;j=nxt[j]) if (in[scc_num[to[j]]] == 1 && scc_num[to[j]] != scc_num[i]) {tag = 1; break;}
if (!tag) {vout--; break;}
}
printf("%.6lf\n",1.0-(double)vout/n);
return 0;
}
为了学习仙人掌才来看的这个，然而现在发现仙人掌用的是无向图的TarjanQAQ
Now I am going away to do my breakfast, when having my breakfast coming again to read more news.
My brother recommended I might like this web site. He was totally
right. This post truly made my day. You cann’t imagine just how
much time I had spent for this information! Thanks!
hello!,I really like your writing very a lot! percentage we keep in touch more approximately your post on AOL?
I require a specialist on this space to resolve my
problem. May be that is you! Taking a look ahead to
peer you.
At this time it sounds like BlogEngine is the preferred blogging platform out there
right now. (from what I’ve read) Is that what you
are using on your blog?
After going over a number of the blog articles on your site, I seriously like your way
of writing a blog. I book-marked it to my bookmark webpage list and will
be checking back soon. Take a look at my website as well and let me know how you feel.
Hey there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m definitely enjoying your blog and look forward to new posts.
Hi there, its good piece of writing about media print,
we all be familiar with media is a fantastic source of data.
Hey there just wanted to give you a quick heads up. The
words in your post seem to be running off the screen in Safari.
I’m not sure if this is a formatting issue or something
to do with browser compatibility but I thought I’d post to let you know.
The design look great though! Hope you get the problem resolved soon.
Thanks
I am really inspired together with your writing abilities
and also with the layout for your weblog. Is this a paid theme or did you customize it your self?
Anyway keep up the excellent quality writing, it’s rare to look a great weblog like this one today..
You ought to take part in a contest for one of the most useful sites on the
web. I am going to highly recommend this website!
Do you have a spam problem on this site; I also am
a blogger, and I was curious about your situation;
many of us have developed some nice practices and we are looking
to trade strategies with others, be sure to shoot me an e-mail if interested.
I am sure this piece of writing has touched
all the internet visitors, its really really good paragraph
on building up new web site.
Hey! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really enjoy your
content. Please let me know. Many thanks
Hi there, I log on to your blog daily. Your humoristic style is witty,
keep it up!
Hey there would you mind stating which blog platform you’re working with?
I’m going to start my own blog soon but I’m having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design and style seems
different then most blogs and I’m looking for something
unique. P.S My apologies for being off-topic but I had to ask!
What’s up, just wanted to say, I liked this article.
It was inspiring. Keep on posting!
Hi to every one, the contents present at this web page are in fact awesome for people experience,
well, keep up the nice work fellows.
Hi , I do believe this is an excellent blog. I stumbled upon it on Yahoo , i will come back once again. Money and freedom is the best way to change, may you be rich and help other people.
When I initially commented I clicked the “Notify me when new comments are added” checkbox and
now each time a comment is added I get several e-mails with the same comment.
Is there any way you can remove people from that service?
Many thanks!
Amazing! Its in fact awesome article, I have got much clear idea
regarding from this piece of writing.
I pay a quick visit every day some sites and blogs to read articles or reviews,
except this webpage presents quality based content.
Hello there! I know this is kinda off topic however , I’d figured I’d
ask. Would you be interested in trading links or maybe guest authoring a blog article or vice-versa?
My blog goes over a lot of the same subjects as yours and I believe
we could greatly benefit from each other. If you’re interested
feel free to shoot me an email. I look forward to hearing from you!
Terrific blog by the way!
I don’t even know how I ended up here, but I thought this post was great.
I do not know who you are but definitely you’re going to
a famous blogger if you aren’t already 😉 Cheers!
I do not even understand how I ended up right here, however I believed this submit was great.
I do not recognise who you are however certainly you’re going to a well-known blogger if you aren’t
already. Cheers!
Hurrah, that’s what I was searching for, what a
stuff! existing here at this blog, thanks admin of this site.
Hi there! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really
enjoy your content. Please let me know. Thank you
My brother recommended I may like this web site.
He used to be entirely right. This submit truly made my day.
You can not consider just how a lot time I had spent for this information! Thanks!
Yes! Finally someone writes about sling tv.
Wonderful blog! Do you have any hints for aspiring writers?
I’m hoping to start my own blog soon but I’m a little
lost on everything. Would you recommend starting with a
free platform like WordPress or go for a paid option? There are so
many choices out there that I’m totally overwhelmed ..
Any recommendations? Thank you!
Hello there! This is kind of off topic but I need some guidance from an established blog.
Is it tough to set up your own blog? I’m not very techincal but I can figure things out pretty
fast. I’m thinking about creating my own but I’m not sure where
to begin. Do you have any tips or suggestions?
With thanks
You completed certain nice points there. I did a search on the subject matter and found nearly all folks will have the same opinion with your blog.