给你一张有向图，问你将任意一条边变成双向后，所能得到的最大强连通分量的大小。
缩点之后，预处理can(i,j)表示i能到j。
之后枚举每一条边(u,v)，再枚举其他所有点t，如果can(u,t) && can(t,v)，则t能和u、v共在一个强连通分量，尝试更新答案。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
bool can[1010][1010];
struct Edge{
int id,v;
};
vector<Edge>G[1010],G2[1010];
vector<int>vs,rG[1010];
int n,m,K;
bool used[1010];
void dfs(int U){
used[U]=1;
for(int i=0;i<G[U].size();++i){
if(!used[G[U][i].v]){
dfs(G[U][i].v);
}
}
vs.push_back(U);
}
int cmp[1010];
void rdfs(int U){
used[U]=1;
cmp[U]=K;
for(int i=0;i<rG[U].size();++i){
if(!used[rG[U][i]]){
rdfs(rG[U][i]);
}
}
}
int a[1010],ans;
void dfs3(int rt,int U){
can[rt][U]=1;
for(int i=0;i<G2[U].size();++i){
if(!can[rt][G2[U][i].v]){
dfs3(rt,G2[U][i].v);
}
}
}
int p,anss[20010];
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
G[x].push_back((Edge){i,y});
rG[y].push_back(x);
}
for(int i=1;i<=n;++i){
if(!used[i]){
dfs(i);
}
}
memset(used,0,sizeof(used));
for(int i=vs.size()-1;i>=0;--i){
if(!used[vs[i]]){
++K;
rdfs(vs[i]);
}
}
for(int i=1;i<=n;++i){
++a[cmp[i]];
}
for(int i=1;i<=K;++i){
ans=max(ans,a[i]);
}
for(int i=1;i<=m;++i){
anss[i]=i;
}
p=m;
for(int i=1;i<=n;++i){
for(int j=0;j<G[i].size();++j){
if(cmp[i]!=cmp[G[i][j].v]){
G2[cmp[i]].push_back((Edge){G[i][j].id,cmp[G[i][j].v]});
}
}
}
for(int i=1;i<=K;++i){
dfs3(i,i);
}
for(int i=1;i<=K;++i){
for(int j=0;j<G2[i].size();++j){
int tmp=a[i]+a[G2[i][j].v];
for(int l=1;l<=K;++l){
if(l!=i && l!=G2[i][j].v && can[i][l] && can[l][G2[i][j].v]){
tmp+=a[l];
}
}
if(tmp>ans){
p=1;
anss[p]=G2[i][j].id;
ans=tmp;
}
else if(tmp==ans){
anss[++p]=G2[i][j].id;
}
}
}
sort(anss+1,anss+p+1);
printf("%d
%d
",ans,p);
for(int i=1;i<p;++i){
printf("%d ",anss[i]);
}
if(p){
printf("%d
",anss[p]);
}
return 0;
}