版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41603898/article/details/102249025
题意：n个点 m条有向边，可以来回走一个点，问在可以逆行一次的情况下最多有能经过多少个不同的点。
解: 先缩点去环建新图，新图建正序(表示以1为起点到达的点)和逆序(以1为终点到达的点) ，然后最长路求出从1到每个点经过不同点的最大数目 正向.f[i]和反向.f[i] ，最后枚举每一条边，计算ans和当前边两点最大值。 输出 ans - sum[belong[1]] ,因为这个重复了。其他细节见代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int N = 300000;
const int inf = 0x7fffffff;
struct NN{
int nxt,v;
}edge[N];
int n,m,num,cnt,head[N],ct;
int low[N],dfn[N],book[N],belong[N],sum[N];
void add(int x,int y){
ct;
edge[ct].v = y;
edge[ct].nxt = head[x];
head[x] = ct;
}
stack<int> s;
struct topo{
struct No{
int v,nxt;
}edge[N];
int ct,in[N],head[N],vis[N];
int f[N];
void add(int x,int y){
ct;
edge[ct].nxt = head[x];
edge[ct].v = y;
head[x] = ct;
in[y] ;
}
void to_Sort(){
queue<int> q;
for(int i=1;i<=n;i ) f[i] = -inf;
//把其他点都设置为负无穷 只有和1所在联通块相连才能更大
f[belong[1]] = sum[belong[1]];
//初始化 防止走不通 f[i] 表示到第 i 块联通分量的最大数目
for(int i=1;i<=n;i ){
if(!in[i])q.push(i);
}
while(!q.empty()){
int v = q.front(); q.pop(); vis[v] = 1;
for(int i=head[v];i;i=edge[i].nxt){
f[edge[i].v] = max(f[edge[i].v],f[v] sum[edge[i].v]);
in[edge[i].v]--;
if(!in[edge[i].v]&&!vis[edge[i].v])q.push(edge[i].v),vis[edge[i].v] = 0;
}
}
}
}pos,neg;
void tarjan(int u){
dfn[u] = low[u] = num;
s.push(u); book[u]=1;
for(int v,i=head[u];i;i=edge[i].nxt){
v = edge[i].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}else if(book[v])low[u] = min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v;
cnt;
do{
v = s.top();
s.pop();
book[v] = 0;
belong[v] = cnt;
sum[cnt] ;
}while(u!=v);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i ){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i )
if(!dfn[i]){
tarjan(i);
}
for(int i=1;i<=n;i ){
for(int v,j=head[i];j;j=edge[j].nxt){
v = edge[j].v;
if(belong[i]!=belong[v]){
pos.add(belong[i],belong[v]);
neg.add(belong[v],belong[i]);
}
}
}
pos.to_Sort();
neg.to_Sort();
int ans = sum[belong[1]];//初始化为一个块个数 防止走不通
for(int i=1;i<=n;i ){
for(int v,j=head[i];j;j=edge[j].nxt){
v = edge[j].v;
if(pos.f[belong[v]]>0&&neg.f[belong[i]]>0)//两点都必须到达
ans = max(ans,pos.f[belong[v]] neg.f[belong[i]]);
}
}
printf("%dn",ans-sum[belong[1]]);
return 0;
}
