- 问题描述
-
老蔡和TT常常约会,他们的约会地点有n个,其中有一些约会地点是相通的,例如地点a到地点b之间有一条路,说明a可以到b,但b不能到a,有一天老菜在思考,怎样才能让这些地点都相互可达呢?因为TT前一刻喜欢在这里,下一刻就想到其他地方了,为了满足TT的愿望,老蔡向你求助,你能帮助他求出他最少要造的路吗?
- 输入
-
第一行包含2个整数,n,m (0<n,m<=100000),代表有n个约会地点,m条路
接下来的m行,每行2个整数a和b,说明a到b有一条路 - 输出
-
老蔡要造的最少的路。
- 样例输入
-
4 3 1 2 1 3 3 4
- 样例输出
-
2
- 提示
-
无
- 来源
-
张超
tarjan求出强连通分量以后缩点,找出所有出度为0的点和入度为0的点,取大者
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<vector> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=100010; struct node { int to; int next; }edge[N]; int head[N]; int tot,index,sccnum,Top,n; int low[N]; int DFN[N]; int block[N]; int in_deg[N]; int out_deg[N]; int Stack[N]; bool instack[N]; void addedge(int from,int to) { edge[tot].to=to; edge[tot].next=head[from]; head[from]=tot++; } void tarjan(int u,int fa) { DFN[u]=low[u]=++index; Stack[Top++]=u; instack[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v=fa) continue; if(!instack[u]) { tarjan(v,u); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],DFN[v]); } if(DFN[u]==low[u]) { sccnum++; do { Top--; block[Stack[Top]]=sccnum; instack[Stack[Top]]=0; }while(u!=Stack[Top]); } } void solve() { memset(low,0,sizeof(low)); memset(DFN,0,sizeof(DFN)); memset(instack,0,sizeof(instack)); memset(in_deg,0,sizeof(in_deg)); memset(out_deg,0,sizeof(out_deg)); index=0; Top=0; sccnum=0; for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i,-1); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=edge[j].next) { if(block[i]!=block[edge[j].to]) { out_deg[block[i]]++; in_deg[block[edge[j].to]]++; } } int a=0,b=0; for(int i=1;i<=sccnum;i++) { if(!in_deg[i]) a++; if(!out_deg[i]) b++; } printf("%d\n",max(a,b)); } int main() { int m; while(~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); tot=0; int s,t; for(int i=1;i<=m;i++) { scanf("%d%d",&s,&t); addedge(s,t); } solve(); } return 0; }