一开始我还天真的一遍DFS求出最长链以为就可以了
不过发现存在有向环，即强连通分量SCC，有向环里的每个点都是可比的，都要分别给个集合才行，最后应该把这些强连通分量缩成一个点，最后保证图里是 有向无环图才行，这个时候再找最长链，当然缩点之后的scc是有权值的，不能只看成1，缩点完了之后，用记忆化搜索DP就可以再On的复杂度内求出结果
所以现学了一下SCC-Tarjan，所谓Scc-tarjan，就是找到强连通分量并且缩点，特别好用，其原理就是利用dfs时间戳，每个点有自己的时间戳，同时再开一个记录通过孩子的路径能指向的最上边的节点的时间戳，lowlink，如果当前lowlink就等于自己，即找到了强连通分量，并且找到了最大的头头。所以一个点也是强连通分量
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; const int N = 100010; stack<int> sta; vector <int> G[N]; vector <int> G4[N]; int vis[N]; int n,m; int pre[N],lowlink[N],sccno[N],w[N],dfs_clk,scc_cnt; int dp[N]; void init() { dfs_clk=scc_cnt=0; for (int i=0;i<=n;i++){ G[i].clear(); pre[i]=0; lowlink[i]=0; sccno[i]=0; vis[i]=0; w[i]=0; G4[i].clear(); } } void dfs(int u) { pre[u]=lowlink[u]=++dfs_clk; sta.push(u); for (int i=0;i<G[u].size();i++){ int v=G[u][i]; if (!pre[v]){ dfs(v); lowlink[u]=min(lowlink[u],lowlink[v]); } else if (!sccno[v]){ lowlink[u]=min(lowlink[u],pre[v]); } } if (lowlink[u]==pre[u]){ scc_cnt++; for (;;){ int x=sta.top();sta.pop(); sccno[x]=scc_cnt; w[scc_cnt]++; if (x==u) break; } } } void tarjan() { for (int i=1;i<=n;i++){ if (!pre[i]) dfs(i); } } void calc(int u) { if (dp[u]!=-1) return; dp[u]=w[u]; int now=w[u]; for (int j=0;j<G4[u].size();j++){ int v=G4[u][j]; calc(v); dp[u]=max(dp[u],dp[v]+now); } } void solve() { for (int i=1;i<=n;i++){ int u=sccno[i]; for (int j=0;j<G[i].size();j++){ int v=sccno[G[i][j]]; if (u!=v) G4[u].push_back(v); } } for (int i=1;i<=scc_cnt;i++){ dp[i]=-1; } for (int i=1;i<=scc_cnt;i++){ calc(i); } int ans=0; for (int i=1;i<=scc_cnt;i++){ ans=max(ans,dp[i]); } printf("%d\n",ans); } int main() { while (scanf("%d%d",&n,&m)!=EOF) { init(); int a,b; while (m--) { scanf("%d%d",&a,&b); G[a].push_back(b); } tarjan(); solve(); } return 0; }
ZOJ 3795 Grouping 强连通分量-tarjan,布布扣,bubuko.com
ZOJ 3795 Grouping 强连通分量-tarjan
原文：http://www.cnblogs.com/kkrisen/p/3902983.html