题目大意:
有n个节点m条边，边都是单向的，请你添加最少的边使得起点s到其他与其他每一个点之间都能互相到达这题一看就是一个缩点啊
其实对于原有的m条边相连的一些点，如果之前他们已经形成了强连通分量(scc)，那么它们之前就可以相互到达(不用修路),对于这些点我们可以把它们“缩”成一个“点”，这其实就是Tarjian缩点的思想
其实luogu里还有很多缩点的模板题,自己去找找吧，都不难的
那么如果你会了缩点，这个题只要缩完点之后统计一下入度为0的点就行了(让强连通分量之间连边)
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef long long ll; const int inf=1e9+7; inline int read() { int p=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();} return f*p;} const int maxn=5007; const int maxm=5007; struct Edge { int next,from,to; }p[maxm]; struct point { int low,dnf,vis,fa,in; }A[maxn]; int n,m,cnt,sum_scc,tot,S; int Stack[maxn],top,ans,head[maxm]; inline void add_edge(int x,int y)//加边 { cnt++; p[cnt].from=head[x]; head[x]=cnt; p[cnt].next=x; p[cnt].to=y; } inline void Tarjian(int x)//Tarjian缩点 { A[x].dnf=A[x].low=++tot; A[x].vis=1,Stack[++top]=x; for(int i=head[x];i;i=p[i].from) { int y=p[i].to; if(!A[y].dnf) Tarjian(y),A[x].low=min(A[x].low,A[y].low); else if(A[y].vis) A[x].low=min(A[x].low,A[y].dnf); } if(A[x].dnf==A[x].low) { int y; sum_scc++; while(y=Stack[top--]) { A[y].vis=0; A[y].fa=sum_scc; if(x==y)break; } } } int main() { n=read(),m=read(),S=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); add_edge(x,y); } for(int i=1;i<=n;i++) if(!A[i].dnf)Tarjian(i); for(int i=1;i<=m;i++)//统计入度 { int x=A[p[i].next].fa,y=A[p[i].to].fa; if(x!=y)A[y].in++; } for(int i=1;i<=sum_scc;i++) //没有入度的scc个数++ if(!A[i].in)ans++; if(!A[A[S].fa].in)ans--; //特判,起点所在的scc如果没有入度那么答案-1 printf("%d ",ans); return 0; }