POJ1236---Network of Schools （强连通分量，缩点，Tarjan算法）

题目来源：https://vjudge.net/problem/POJ-1236

题意

给出一个有向图，从第2行一直到n+1行表示从当前点当能够到达当前行的每一个点，输出两个结果： 问：若是走完全图，需要至少从几个点出发？ 问：至少需要添加几条边，才可以使得在任意一点都可以到达整个图的任意一个地方？

思路

最近在学图的连通问题，理解能力较差，两天终于学会了一些零碎的知识点，索性总结一下，也可以给其他人铺点路（轻喷）。 这道题牵扯出一个新的名词：强连通分量。 学习Tarjan算法推荐博客：https://www.byvoid.com/zhs/blog/scc-tarjan 总的来说，这些算法其实就是利用深搜的模拟过程，思想也不是那么难懂，强连通就是指在有向图里，给出两个点，这两点可以直接或间接相互到达，而第二问翻译过来就是需要几条边才可以使得全图成为一个强连通分量，第一问就是如果图可以分成好几个强连通分量，那么入度为0的有几个。 如果最后能够知道哪个点在哪个强联通分量里，就可以标上数字，用一个容器装一下，代码里我用的是mp数组，而这就是缩点。 下面是一些好博客，可以节省入门的时间： http://www.cnblogs.com/llhthinker/p/4954082.html https://www.byvoid.com/zhs/blog/biconnect

代码

#include<cstdio> #include<vector> #include<map> #include<stack> #include<cstring> #include<algorithm> using namespace std; const int N=100+10; struct pp { int to,next; }edge[N*N]; int first[N]; int low[N],num[N]; int IN[N],OUT[N],mp[N]; int n,Num,SCC_num; stack<int> s; void Tarjan(int u) { num[u]=low[u]=Num++; s.push(u); for(int i=first[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!num[v]) { Tarjan(v); low[u]=min(low[v],low[u]); } else if(!mp[v]) { low[u]=min(low[u],num[v]); } } if(low[u]==num[u])//一个强联通分量的点（根） { while(1) { int w=s.top(); s.pop(); mp[w]=SCC_num;//缩点操作进行标号 if(w==u) { SCC_num++; break; } } } } void init() { while(!s.empty()) s.pop(); memset(low,0,sizeof(low)); memset(num,0,sizeof(num)); memset(IN,0,sizeof(IN)); memset(OUT,0,sizeof(OUT)); memset(mp,0,sizeof(mp)); Num=SCC_num=1; for(int i=1;i<=n;i++) { if(!num[i]) Tarjan(i); } } int main() { while(~scanf("%d",&n)) { int tot=0; for(int i=1;i<=n;i++) { int ed; first[i]=-1; while(~scanf("%d",&ed)&&ed) { edge[tot].to=ed; edge[tot].next=first[i]; first[i]=tot++; } } init(); int in=0,out=0; for(int i=1;i<=n;i++) { for(int j=first[i];j!=-1;j=edge[j].next) { if(mp[i]!=mp[edge[j].to])//求每一个强联通分量的入度和出度 { IN[mp[edge[j].to]]++; OUT[mp[i]]++; } } } for(int i=1;i<SCC_num;i++) { if(IN[i]==0) in++; if(OUT[i]==0) out++; } printf("%d\n",in); if(SCC_num==2) printf("0\n");//如果只有一个强联通分量，那就不用添加边就可以了 else printf("%d\n",max(in,out)); } }