Gym - 101170B British Menu (强连通缩点+dp)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int n,m,hd[N],ne,low[N],dfn[N],nscc,scc[N],siz[N],sta[N],tp,tot;
 5 int id[N],ID[N][5],G[N][5][5],len[N][5][5],vis[5],dp[N][5][2];
 6 struct E {int v,nxt;} e[(int)1e6+10];
 7 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
 8 void Tarjan(int u) {
 9     low[u]=dfn[u]=++tot,sta[++tp]=u;
10     for(int i=hd[u]; ~i; i=e[i].nxt) {
11         int v=e[i].v;
12         if(!dfn[v])Tarjan(v),low[u]=min(low[u],low[v]);
13         else if(!scc[v])low[u]=min(low[u],dfn[v]);
14     }
15     if(low[u]==dfn[u])for(++nscc; !scc[u];) {
16             int v=sta[tp--];
17             scc[v]=nscc,id[v]=siz[nscc]++,ID[scc[v]][id[v]]=v;
18         }
19 }
20 void dfs(int u,int l,int sc,int fr) {
21     if(vis[u])return;
22     vis[u]=1;
23     len[sc][fr][u]=max(len[sc][fr][u],l);
24     for(int i=0; i<siz[sc]; ++i)if(G[sc][u][i])dfs(i,l+1,sc,fr);
25     vis[u]=0;
26 }
27 int dfs2(int sc,int u,int f) {
28     int& ret=dp[sc][u][f];
29     if(~ret)return ret;
30     ret=0;
31     int U=ID[sc][u];
32     for(int i=hd[U]; ~i; i=e[i].nxt) {
33         int V=e[i].v,v=id[V];
34         if(scc[U]!=scc[V])ret=max(ret,dfs2(scc[V],v,0)+1);
35     }
36     if(!f)for(int v=0; v<siz[sc]; ++v)if(len[sc][u][v])
37                 ret=max(ret,dfs2(sc,v,1)+len[sc][u][v]);
38     return ret;
39 }
40 void getscc() {
41     memset(siz,0,sizeof siz);
42     memset(dfn,0,sizeof dfn);
43     tot=nscc=0,tp=-1;
44     for(int i=1; i<=n; ++i)if(!dfn[i])Tarjan(i);
45 }
46 int main() {
47     memset(hd,-1,sizeof hd),ne=0;
48     scanf("%d%d",&n,&m);
49     while(m--) {
50         int u,v;
51         scanf("%d%d",&u,&v);
52         addedge(u,v);
53     }
54     getscc();
55     memset(G,0,sizeof G);
56     for(int u=1; u<=n; ++u) {
57         for(int i=hd[u]; ~i; i=e[i].nxt) {
58             int v=e[i].v;
59             if(scc[u]==scc[v])G[scc[u]][id[u]][id[v]]=1;
60         }
61     }
62     for(int i=1; i<=nscc; ++i)
63         for(int j=0; j<siz[i]; ++j)dfs(j,0,i,j);
64     memset(dp,-1,sizeof dp);
65     int ans=0;
66     for(int i=1; i<=n; ++i)ans=max(ans,dfs2(scc[i],id[i],0));
67     printf("%d\n",ans+1);
68     return 0;
69 }