题意
有一个有向图，允许最多走一次逆向的路，问从1再走回1，最多能经过几个点。
思路
（一）
首先先缩点。自己在缩点再建图中犯了错误，少连接了大点到其他点的边。
跑两次最长路，一次以1为起点，一次以1为终点（跑一遍反图）
然后枚举边，判断可否形成一个环。
（二）
分层图的思想
以为只有一次逆向的机会，可以建两层图，第一层向第二层连翻转的情况。
#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> /* ⊂_ヽ ＼＼ Λ＿Λ 来了老弟 ＼('ㅅ') > ⌒ヽ / へ＼ / / ＼＼ ﾚ ノ ヽ_つ / / / /| ( (ヽ | |、＼ | 丿 ＼ ⌒) | | ) / 'ノ ) Lﾉ */ using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue typedef long long ll; typedef unsigned long long ull; //typedef __int128 bll; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q //priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q #define fi first #define se second //#define endl ' ' #define boost ios::sync_with_stdio(false);cin.tie(0) #define rep(a, b, c) for(int a = (b); a <= (c); ++ a) #define max3(a,b,c) max(max(a,b), c); #define min3(a,b,c) min(min(a,b), c); const ll oo = 1ll<<17; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); const double PHI=0.61803399; //黄金分割点 const double tPHI=0.38196601; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } inline void cmax(int &x,int y){if(x<y)x=y;} inline void cmax(ll &x,ll y){if(x<y)x=y;} inline void cmin(int &x,int y){if(x>y)x=y;} inline void cmin(ll &x,ll y){if(x>y)x=y;} /*-----------------------showtime----------------------*/ const int maxn = 1e5+9; vector<int>mp1[maxn],mp2[2][maxn]; int dfn[maxn],low[maxn],vis[maxn],gtot,nn,dp[maxn]; int col[maxn],vv[maxn]; stack<int>st; void tarjan(int u){ dfn[u] = low[u] = ++gtot; st.push(u); vis[u] = 1; for(int i=0; i<mp1[u].size(); i++){ int v = mp1[u][i]; if(dfn[v] == 0) { tarjan(v); low[u] = min(low[u], low[v]); } else if(vis[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ int x;nn++; while(!st.empty()){ int x = st.top(); st.pop(); col[x] = nn; vis[x] = 0; dp[nn]++; if(x == u) break; } } } int ans = 0; int dis[maxn][2]; pii edge[maxn]; void dji(int s,int id){ priority_queue<pii>que; dis[s][id] = dp[s]; que.push(pii(dis[s][id], s)); while(!que.empty()){ int u = que.top().se; que.pop(); for(int i=0; i<mp2[id][u].size(); i++) { int v = mp2[id][u][i],w = dp[v]; if(dis[v][id] < dis[u][id] + w){ dis[v][id] = dis[u][id] + w; que.push(pii(dis[v][id], v)); } } } } int main(){ int n,m; scanf("%d%d", &n, &m); rep(i, 1, m) { int x,y; scanf("%d%d", &x, &y); mp1[x].pb(y); edge[i] = pii(x, y); } for(int i=1; i<=n; i++) if(!dfn[i])tarjan(i); int s = col[1]; int pp = 0; memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; i++){ int u = col[i]; if(u == 0) continue; for(int j=0; j<mp1[i].size(); j++){ int v = col[mp1[i][j]]; if(v == 0 || u == v) continue; mp2[0][u].pb(v); mp2[1][v].pb(u); } } dji(s, 0); dji(s, 1); int ans = dp[s]; for(int i=1; i<=m; i++){ int u = col[edge[i].fi],v = col[edge[i].se]; if(dis[v][0] && dis[u][1])ans = max(ans, dis[v][0] + dis[u][1] - dp[s]); } printf("%d ", ans); return 0; }