【CF522A】Reposts

时间:2022-10-14 20:19:21

题目大意:给定一个有向图,求图中最长路。

题解:直接拓扑排序后按照拓扑序枚举即可。处理时应将字符串通过 map 映射成一个点,同时注意字符串大小写转换,C++ string 中没有提供直接大小写转换的函数,因此需要自己手动遍历,进行 \(tolower()\) 函数调用。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=410; map<string,int> mp;
int n,cnt,ans,d[maxn],indeg[maxn],topo[maxn],sum;
struct node{
int nxt,to;
}e[maxn];
int tot=1,head[maxn];
inline void add_edge(int from,int to){
e[++tot]=node{head[from],to},head[from]=tot,++indeg[to];
} inline void handle(string& s){
for(int i=0;i<s.size();i++)s[i]=tolower(s[i]);
} void read_and_parse(){
cin>>n;
string from,no,to;
for(int i=1;i<=n;i++){
cin>>to>>no>>from;
handle(to),handle(from);
if(mp.find(from)==mp.end())mp.insert(make_pair(from,++cnt));
if(mp.find(to)==mp.end())mp.insert(make_pair(to,++cnt));
add_edge(mp[from],mp[to]);
}
} void topo_sort(){
queue<int> q;
for(int i=1;i<=cnt;i++)if(!indeg[i])q.push(i);
while(q.size()){
int u=q.front();q.pop();
topo[++sum]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;--indeg[v];
if(!indeg[v])q.push(v);
}
}
} void solve(){
topo_sort();
for(int i=sum;i>=1;i--){
d[i]=1;
for(int j=head[i];j;j=e[j].nxt)d[i]=max(d[i],d[e[j].to]+1);
ans=max(ans,d[i]);
}
printf("%d\n",ans);
} int main(){
read_and_parse();
solve();
return 0;
}