cf Substring(dfs,判环)

给出一个有向图,每个点标一个字母,问你找到一条路径,使得这条路径上出现的某个字母出现次数最多的最大值.
5 4
abaca
1 2
1 3
3 4
4 5
这题的思路是不难想的,一个树上dp,每个父节点用子节点返还的信息更新自己,表达数据为从本处往下走,任何一种字母,最多经过多少次.
但是本题要判一下环,有向图的判联通是这样.

bool huan = false;
void ph(int u)
{
if(huan||vis[u]==1) return;//为了防止反复判已判的点.
if(vis[u]==-1) huan = true;
vis[u] = -1;
for (int i = 0; i < G[u].size(); ++i)
ph(G[u][i]);
vis[u] = 1;
}

for (int i = 0; i < n; ++i)
{
if(vis[i]==0)
{
ph(i);
if(huan) return cout<<"-1"<<endl,0;
}
}

因为没加注释的那一句,我t了很久,开始以为是我vector dfs太慢,后来发现其实不是的,如果不加,就会重复判很多次.
太菜了,复杂度算不出,大概是n+m吧.

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 3e5+17;
string str;
vector<int > G[MAXN],use[MAXN];
int vis[MAXN];
map<pair<int,int >,int > mp;
vector<int > dfs(int u)
{
if(vis[u])
{
return use[u];
}
else
{
vector<int > now(26,0);
vis[u] = 1;
if(G[u].size()==0)
{
now[str[u]-'a']++;
use[u] = now;
return now;
}
vector<int > son;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
son = dfs(v);
for (int i = 0; i < 26; ++i)
now[i] = max(now[i],son[i]);
}
now[str[u]-'a']++;
use[u] = now;
return now;
}
}
bool huan = false;
void ph(int u)
{
if(huan||vis[u]==1) return;//为了防止反复判已判的点.
if(vis[u]==-1) huan = true;
vis[u] = -1;
for (int i = 0; i < G[u].size(); ++i)
ph(G[u][i]);
vis[u] = 1;
}
int in[MAXN];
int main(int argc ,char const *argv[])
{
#ifdef GoodbyeMonkeyKing
freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
#endif
int n,m;
cin>>n>>m>>str;
for (int i = 0; i < m; ++i)
{
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
if(mp[{u,v}]!=1)
{
mp[{u,v}]=1;
G[u].push_back(v);
in[v]++;
}
}
for (int i = 0; i < n; ++i)
{
if(vis[i]==0)
{
ph(i);
if(huan) return cout<<"-1"<<endl,0;
}
}
memset(vis, 0, sizeof(vis));
int ans = 0;
for (int i = 0; i < n; ++i)
{
if(in[i]==0)
{
vector<int > gt = dfs(i);
for (int i = 0; i < 26; ++i)
ans = max(gt[i],ans);
}
}
cout<<ans<<endl;
return 0;
}

真tm菜,真tm菜.

最后

以上就是腼腆冬天为你收集整理的cf Substring(dfs,判环)的全部内容，希望文章能够帮你解决cf Substring(dfs,判环)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。