2、追捕
【题目背景】
Duan2baka：“jmsyzsfq天下第一蠢！”
jmsyzsfq：“你说什么？！”
【题目描述】
于是Duan2baka开始了逃亡的旅程，而jmsyzsfq也开始追捕Duan2baka。 他们来到了一个有n个节点的有向图，迅速逃跑的Duan2baka会首先降落在有向图的某个节点T上，因为怕发出声音，他会永远静止不动。而随后跟来的jmsyzsfq会降落在图上随机一个节点S上（可以与T相同），并可以沿着图中的有向边随意走动。因为jmsyzsfq有着敏锐的嗅觉而且绝顶聪明，他一定会沿着正确的方向寻找Duan2baka。你可以认为，如果图中存在一条合法的从S到T的路径，那么jmsyzsfq一定会抓到Duan2baka——因此jmsyzsfq能否追捕到Duan2baka在他刚刚降落在图上的时候就已经确定了。现在请你帮帮jmsyzsfq，在他降落前告诉他有多大的概率能够追捕到Duan2baka，并告诉他想要追到Duan2baka他可以降落在哪些节点上。
【输入格式】
输入第一行包含三个整数n，m，opt，表示图中有n个节点，m条有向边；opt为0或1，含义见输出格式所述。
输入第2至m+1行每行两个整数u，v描述了图中一条从u到v的有向边。
输入第m+2行一个整数T表示Duan2baka降落的位置。
【输出格式】
如果输入的opt为0，只需要输出jmsyzsfq能够追捕到Duan2baka的概率。
如果输入的opt为1，输出两行，第一行输出jmsyzsfq能够追捕到Duan2baka的概率；第二行按从小到大输出想要追到Duan2baka他可以降落的节点编号，编号间用空格隔开。
对于jmsyzsfq能够追捕到Duan2baka的概率，是一个既约分数，形如“a/b”（a，b为整数），使gcd(a,b)=1，如果a=b,输出1/1。
【样例1输入】
9 10 1
1 2
2 1
2 4
6 1
9 6
6 5
5 3
3 7
3 1
1 8
1
【样例1输出】
2/3
1 2 3 5 6 9
【样例1解释】
图*9个节点，能够到达节点S=1的节点共6个：{1,2,3,5,6,9}。所以能够追捕到Duan2baka的概率为6/9=2/3。
【样例2输入】
5 7 1
1 2
1 3
1 5
2 4
4 1
4 5
5 3
1
【样例2输出】
3/5
1 2 4
【数据范围与约定】
opt=0和opt=1的数据各50%。
对于opt=0和opt=1的情况，有着完全相同的子任务：
对于10%的数据，n,m≤100。
对于另外30%的数据，n,m≤100,000。
对于另外10%的数据，保证图是一个完全图，即对于任意两个点u和v，必然有两条有向边u→v和v→u。
对于另外20%的数据，保证图是一个有向无环图，即对于任意一个点x，不存在图上一条路径从x经过其它点后回到x。
对于另外20%的数据，保证如果图上存在一条边u→v，一定存在一条边v→u。
对于100%的数据，n,m≤1,000,000，保证数据合法且不存在重边、自环。
思路：
有大佬广搜秒切
本蒟蒻表示想复杂了
我先用tarjan缩了一遍点，然后建反图
因为求可达他的点，就是求他可达的点
然后dfs扫一遍就好了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
using namespace std;
int low[],dfn[],sta[],tot,bnt;
int top,n,m,head[],color[],opt,cnt;
int vis[],pl,bj[];
struct ljb{
int to,nxt;
}x[];
struct cb{
int from,to;
}y[];
inline void add(int from,int to)
{
bnt++;
x[bnt].to=to;
x[bnt].nxt=head[from];
head[from]=bnt;
}
void tarjan(int wz)
{
cnt++;
low[wz]=cnt;
dfn[wz]=cnt;
top++;
sta[top]=wz;
vis[wz]=;
for(rii=head[wz];i!=;i=x[i].nxt)
{
int ltt=x[i].to;
if(dfn[ltt]==)
{
tarjan(ltt);
low[wz]=min(low[wz],low[ltt]);
}
else
{
if(vis[ltt]!=)
{
low[wz]=min(low[wz],dfn[ltt]);
}
}
}
if(low[wz]==dfn[wz])
{
tot++;
while(sta[top+]!=wz)
{
color[sta[top]]=tot;
vis[sta[top]]=;
top--;
}
}
}
void dfs(int wz)
{
bj[wz]=;
for(rii=head[wz];i!=;i=x[i].nxt)
{
int ltt=x[i].to;
if(bj[ltt]==)
{
dfs(ltt);
}
}
}
int main()
{
freopen("hunt.in","r",stdin);
freopen("hunt.out","w",stdout);
scanf("%d%d%d",&n,&m,&opt);
for(rii=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
y[i].from=from;
y[i].to=to;
add(from,to);
}
for(rii=;i<=n;i++)
{
if(dfn[i]==)
{
tarjan(i);
}
}
memset(x,,sizeof(x));
memset(head,,sizeof(head));
bnt=;
for(rii=;i<=m;i++)
{
int from=y[i].from;
int to=y[i].to;
if(color[from]!=color[to])
{
add(color[to],color[from]);
}
}
scanf("%d",&pl);
dfs(color[pl]);
int cnt=;
for(rii=;i<=n;i++)
{
if(bj[color[i]]==)
{
cnt++;
}
}
int gc=__gcd(cnt,n);
cout<<cnt/gc<<"/"<<n/gc<<endl;
if(opt==)
{
for(rii=;i<=n;i++)
{
if(bj[color[i]]==)
{
printf("%d ",i);
}
}
}
}
（其实不缩点也完全可以）