此篇文章的整理仅用于学习记录，供日后复习，大部分内容来源于北大郭炜老师整理的课件。
有关tarjan算法的一个结论：求几个点的LCA等价于求dfn[]最小的节点和dfn[]最大的这两个节点的LCA.
1.POJ2186:Popular Cows
题意：给定一个有向图，求有多少顶点是由任何顶点出发都可达的。
有用的定理：有向无环图中唯一出度为0的点，一定可以有任何点出发均可达（由于无环，所以从任何点出发往前走必然终止于一个出度为0的点）。
解题思路：1.求出所有强连通分量；
2.每个强连通分量缩成一个点，则形成一个有向无环图DAG。
3.DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。那么该点所代表的连通分量上的所有的原图中的点，都能被原图中的所有点可达，则该连通分量的点数，就是答案。
4.DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0.
?缩点的时候不一定要构造新图，只要把不同强连通分量的点染不同颜色，然后考察各种颜色的点有没有连到别的颜色的边即可(即其对应的缩点后的DAG图上的点是否有出边）。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1e4+10;
const int maxm=5e4+10;
int n,m,dfn[maxn],low[maxn],tot=0,stck[maxn],r=0,sccnum=0,scc[maxn],sum[maxn];
int outd[maxn]; //出度
vector<int> sons[maxn];void tarjan(int u){dfn[u]=low[u]=++tot;stck[++r]=u;for(int i=0;i<sons[u].size();i++){int v=sons[u][i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!scc[v]){ //scc[v]表明该强连通分量还在栈中 low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int len=r;sccnum++; //染色编号while(stck[r]!=u) scc[stck[r--]]=sccnum; //缩点 scc[u]=sccnum;r--;sum[sccnum]=len-r; //该强连通分量中总的结点数 //cout<<"len-r="<<len-r<<",len="<<len<<",r="<<r<<endl;//printf("sum[%d]=%d\n",sccnum,sum[sccnum]);}
}int main(){scanf("%d%d",&n,&m);int x,y;for(int i=0;i<m;i++){scanf("%d%d",&x,&y);sons[x].push_back(y);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=n;i++){for(int j=0;j<sons[i].size();j++){int v=sons[i][j];if(scc[i]!=scc[v]) outd[scc[i]]++;}}int ans=0;bool flag=false;//cout<<"sccnum="<<sccnum<<endl;for(int i=1;i<=sccnum;i++){//cout<<"sum["<<i<<"]="<<sum[i]<<endl;if(outd[i]==0) {if(!flag){ans=sum[i];flag=true;}else{ans=0;break;}}}printf("%d\n",ans);return 0;
}
2.POJ1236: Network of Schools
题意：N（2<N<100）各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：出事至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。问题2：至少需要添加几条传输线路（边），使任意向一个学校发放软件后，经过若干次传送，网络内所有学校最终都能得到软件。
抽离出模型：给定一个有向图，求：
1）至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
2）至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
顶点数<=100
有用的定理：有向无环图中所有入度不为0的点，一定可以由某个入度为0的点出发可达。（由于无环，所以从任何入度不为0的点往回走，必然终止于一个入度为0的点）
解题思路：
- Tarjan算法求SCC，并缩点建图
- 对于问题1，缩点后的图中入度为0点的点数即是答案
- 对于问题2，答案为max（入度为0的点的点数，出度为0的点的点数），因为对于每个入度或出度为0的点，需要连一条边来解决，那么将出度为0的点连向入度为0的点是最优的。
- 此外，如果最后SCC只有一个，那么问题二的答案应该特判为0.
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=110;
const int INF=0x3f3f3f3f;
vector<int> E[maxn];
int n,dfn[maxn],low[maxn],tot,scc[maxn],sccnum;
int ind[maxn],outd[maxn];
stack<int> s;void tarjan(int u){dfn[u]=low[u]=++tot;s.push(u);int length=E[u].size();for(int i=0;i<length;i++){int v=E[u][i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!scc[v]){ //scc[v]==0表明该节点v还在栈中 low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int v;sccnum++;do{v=s.top();s.pop();scc[v]=sccnum;}while(u!=v);}}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x;while(scanf("%d",&x)&&x!=0){E[i].push_back(x);}}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=n;i++){for(int j=0;j<E[i].size();j++){int u=E[i][j];if(scc[i]!=scc[u]){ind[scc[u]]++;outd[scc[i]]++;}}}int zeroIndegree=0,zeroOutdegree=0;for(int i=1;i<=sccnum;i++){if(ind[i]==0) zeroIndegree++;if(outd[i]==0) zeroOutdegree++;}if(sccnum==1) printf("1\n0\n");else printf("%d\n%d\n",zeroIndegree,max(zeroIndegree,zeroOutdegree));return 0;
}