很 明 显 的 拓 扑 排 序 呀 ! ! 很明显的拓扑排序呀!! 很明显的拓扑排序呀!!
从 没 有 出 边 的 点 开 始 往 上 d p 从没有出边的点开始往上dp 从没有出边的点开始往上dp
每 次 维 护 一 个 d p [ i ] [ j ] 表 示 到 i 点 字 母 j 的 最 多 次 数 每次维护一个dp[i][j]表示到i点字母j的最多次数 每次维护一个dp[i][j]表示到i点字母j的最多次数
如 果 有 环 说 明 图 中 可 以 无 限 循 环 , 输 出 − 1 如果有环说明图中可以无限循环,输出-1 如果有环说明图中可以无限循环,输出−1
注 意 拓 扑 中 对 于 一 个 点 v , 要 把 所 有 父 节 点 更 新 注意拓扑中对于一个点v,要把所有父节点更新 注意拓扑中对于一个点v,要把所有父节点更新
不 管 那 个 父 节 点 是 否 在 本 次 入 队 不管那个父节点是否在本次入队 不管那个父节点是否在本次入队
#include <bits/stdc++.h> using namespace std; const int maxn=3e5+20; vector<int>vec[maxn]; int in[maxn],dp[maxn][33],ans=1,now,n,m; char a[maxn]; queue<int>q; int main() { cin >> n >> m >>(a+1); for(int i=1,l,r;i<=m;i++) { scanf("%d%d",&l,&r); vec[r].push_back(l);//拓扑排序使用 in[l]++;//出度加加 } for(int i=1;i<=n;i++) if(in[i]==0) q.push(i),dp[i][a[i]-'a']=1; while(!q.empty()) { now++; int u=q.front();q.pop(); for(int i=0;i<vec[u].size();i++) { int v=vec[u][i]; if(--in[v]==0) q.push(v); for(int j=0;j<=25;j++) { int s=dp[u][j]+(a[v]==char('a'+j)); dp[v][j]=max(dp[v][j],s); ans=max(ans,dp[v][j]); } } } if(now<n) cout<<-1; else cout<<ans; }