爆炸代码又调出一些错误
```cpp
#include <bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=3e5+10;
int n,m,a[N],ans,top,dfn[N],low[N],l=1,r=0,st[N],cnt,b[N],f1[N],f2[N],u_[N],v_[N],S[N],q[N];
vector<int> g[N],G[N],G_[N],g1,g2;
bool vis[N];
void tarjan(int u)
{
dfn[u]=low[u]=++top;
st[++r]=u;
vis[u]=1;
for(int i = 0;i<g[u].size();i++){
int v=g[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){//返祖
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
cnt++;
while(st[r]!=u){
vis[st[r]]=0;
// cout << cnt << '\n';
b[st[r]]=cnt;
S[cnt]++;
r--;
}
vis[u]=0;
//cout << cnt << '\n';
b[u]=cnt;
S[cnt]++;
r--;
}
return;
}
struct Node
{
int id,sum,wsr;
};
bool operator<(const Node&a,const Node&b)
{
return a.sum<b.sum;
}
//priority_queue<Node>q;
/*
inline void dij(int rt)//dij跑缩后的最长路
{
dis[rt][0]=S[rt];
q.push({rt,S[rt],0});
// vis[rt]=1;
for(;q.size();){
Node u=q.top();
q.pop();
// cout << u.id << " " << u.sum << " " << u.wsr << '\n';
///if(vis[u.id]) continue;
//vis[u.id]=1;
for(int i = 0;i<G_[u.id].size();i++){
int v=G_[u.id][i];
if(u.wsr==0){
if(dis[v][1]<dis[u.id][0]+S[v]){
dis[v][1]=dis[u.id][0]+S[v];
q.push({v,dis[v][1],1});
}
}
}
for(int i = 0;i<G[u.id].size();i++){
int v=G[u.id][i];
if(u.wsr!=0){
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
else{
if(dis[v][0]<dis[u.id][0]+S[v]){
dis[v][0]=dis[u.id][0]+S[v];
q.push({v,dis[v][0],0});
}
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
}
}
}*/
inline void add(int ui,int vi)//原图
{
g[ui].push_back(vi);
//g[vi].push_back(ui);
return;
}
inline void add1(int ui,int vi)//缩完点的图
{
G[ui].push_back(vi);
G_[vi].push_back(ui);
}
inline void solve()
{
n=read(),m=read();
F(i,1,m){
u_[i]=read(),v_[i]=read();
add(u_[i],v_[i]);
}
//dij(1);
for(int i=1;i<=n;i++) {
if(!dfn[i]){
tarjan(i);
}
}
// F(i,1,n) if(b[i]==0) b[i]=++cnt,S[cnt]=1;
// cout << l << " " << r << '\n';
// F(i,1,n) cout << b[i] << '\n';
// F(i,1,cnt)
// {
// cout << i << " " << S[i] << '\n';
// }
F(i,1,m){
int ui=u_[i],vi=v_[i];
if(b[ui]!=b[vi]){//两个不属于同一个强连通分量
//bdcdcout << ui << " " << vi << '\n';
//cout << b[ui] << " " << b[vi] << '\n';
//cout << "------------------------\n";
g1.push_back(ui);
g2.push_back(vi);
add1(ui,vi);
}
}
l=1,r=0;
q[++r]=b[1];
f1[b[1]]=0;
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G[u].size();i++){
int v=G[u][i];
f1[v]=max(f1[u]+S[v],f1[v]);
q[++r]=v;
}
}
l=1,r=0;
q[++r]=b[1];
f2[b[1]]=1;
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G_[u].size();i++){
int v=G_[u][i];
f2[v]=max(f2[v],f2[u]+S[v]);
q[++r]=v;
}
}
int maxn=0;
for(int i = 0;i<g1.size();i++){
int ui=g1[i],vi=g2[i];
maxn=max(maxn,f1[ui]+f2[vi]);
maxn=max(maxn,f1[vi]+f2[ui]);
}
cout << maxn;
}
signed main()
{
solve();
return 0;
}
```
by Reply_ @ 2023-07-20 20:02:03
@[Reply_](/user/373530) 看出的几个错误先跟你说了吧
1.建缩点完后的图应以强联通分量为点
2.没有考虑1所在的强联通分量的大小
by operator_ @ 2023-07-21 08:10:22
@[operator_](/user/499682)
大佬NB,但改完后RE3个点,能不能帮忙调一下
```cpp
#include <bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=1e6+10;
int n,m,a[N],ans,top,dfn[N],low[N],l=1,r=0,st[N],cnt,b[N],f1[N],f2[N],u_[N],v_[N],S[N],q[N];
vector<int> g[N],G[N],G_[N],g1,g2;
bool vis[N];
void tarjan(int u)
{
dfn[u]=low[u]=++top;
st[++r]=u;
vis[u]=1;
for(int i = 0;i<g[u].size();i++){
int v=g[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){//返祖
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
cnt++;
while(st[r]!=u){
vis[st[r]]=0;
// cout << cnt << '\n';
b[st[r]]=cnt;
S[cnt]++;
r--;
}
vis[u]=0;
//cout << cnt << '\n';
b[u]=cnt;
S[cnt]++;
r--;
}
return;
}
struct Node
{
int id,sum,wsr;
};
bool operator<(const Node&a,const Node&b)
{
return a.sum<b.sum;
}
//priority_queue<Node>q;
/*
inline void dij(int rt)//dij跑缩后的最长路
{
dis[rt][0]=S[rt];
q.push({rt,S[rt],0});
// vis[rt]=1;
for(;q.size();){
Node u=q.top();
q.pop();
// cout << u.id << " " << u.sum << " " << u.wsr << '\n';
///if(vis[u.id]) continue;
//vis[u.id]=1;
for(int i = 0;i<G_[u.id].size();i++){
int v=G_[u.id][i];
if(u.wsr==0){
if(dis[v][1]<dis[u.id][0]+S[v]){
dis[v][1]=dis[u.id][0]+S[v];
q.push({v,dis[v][1],1});
}
}
}
for(int i = 0;i<G[u.id].size();i++){
int v=G[u.id][i];
if(u.wsr!=0){
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
else{
if(dis[v][0]<dis[u.id][0]+S[v]){
dis[v][0]=dis[u.id][0]+S[v];
q.push({v,dis[v][0],0});
}
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
}
}
}*/
inline void add(int ui,int vi)//原图
{
g[ui].push_back(vi);
//g[vi].push_back(ui);
return;
}
inline void add1(int ui,int vi)//缩完点的图
{
G[ui].push_back(vi);
G_[vi].push_back(ui);
}
inline void solve()
{
n=read(),m=read();
F(i,1,m){
u_[i]=read(),v_[i]=read();
add(u_[i],v_[i]);
}
//dij(1);
for(int i=1;i<=n;i++) {
if(!dfn[i]){
tarjan(i);
}
}
// F(i,1,n) if(b[i]==0) b[i]=++cnt,S[cnt]=1;
// cout << l << " " << r << '\n';
// F(i,1,n) cout << b[i] << '\n';
// F(i,1,cnt)
// {
// cout << i << " " << S[i] << '\n';
// }
F(i,1,m){
int ui=u_[i],vi=v_[i];
if(b[ui]!=b[vi]){//两个不属于同一个强连通分量
//bdcdcout << ui << " " << vi << '\n';
//cout << b[ui] << " " << b[vi] << '\n';
//cout << "------------------------\n";
g1.push_back(b[ui]);
g2.push_back(b[vi]);
add1(b[ui],b[vi]);
}
}
memset(f1,-0x3f,sizeof f1);
memset(f2,-0x3f,sizeof f2);;
l=1,r=0;
q[++r]=b[1];
f1[b[1]]=S[b[1]];
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G[u].size();i++){
int v=G[u][i];
f1[v]=max(f1[u]+S[v],f1[v]);
q[++r]=v;
}
}
l=1,r=0;
q[++r]=b[1];
f2[b[1]]=0;
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G_[u].size();i++){
int v=G_[u][i];
f2[v]=max(f2[v],f2[u]+S[v]);
q[++r]=v;
}
}
int maxn=S[b[1]];
for(int i = 0;i<g1.size();i++){
int ui=g1[i],vi=g2[i];
maxn=max(maxn,f1[ui]+f2[vi]);
maxn=max(maxn,f1[vi]+f2[ui]);
}
cout << maxn;
}
signed main()
{
solve();
return 0;
}
```
by Reply_ @ 2023-07-21 08:34:02
@[Reply_](/user/373530) 求2个最短路的那里爆队列了,改成STL就没RE了
但我这里测了一下又TLE了一个点,应该是不能用BFS,改成SPFA吧,我觉得应该就好了。
~~(你可以试试手写循环队列能不能卡过)~~
by operator_ @ 2023-07-21 08:51:39
@[operator_](/user/499682) thx,但现在上课,暂时改不了
by Reply_ @ 2023-07-21 09:27:05
@[operator_](/user/499682)
大佬蟹蟹,吸氧就过了
by Reply_ @ 2023-07-21 11:46:11