用的是 Kosaraju 会有问题吗?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int mazesize = 505;
int mat[mazesize][mazesize];
int w, l;
vector<int> G[mazesize << 2];
vector<int> rG[mazesize << 2];
vector<int> ord;
int scccnt = 0;
bool used[mazesize << 2];
int color[mazesize << 2];
void dfs1(int u)
{
used[u] = true;
for(int v : G[u])
{
if(!used[v])
{
dfs1(v);
}
ord.push_back(u);
}
}
void dfs2(int u)
{
color[u] = scccnt;
for(int v : rG[u])
{
if(!color[v])
{
dfs2(v);
}
}
}
void two2one(int x, int y, int nx, int ny)
{
if(nx > l || nx < 1 || ny > w || ny < 1 || mat[x][y] < mat[nx][ny])
{
return;
}
G[(x - 1) * w + y].push_back((nx - 1) * w + ny);
rG[(nx - 1) * w + ny].push_back((x - 1) * w + y);
}
int Kosaraju()
{
scccnt = 0;
for(int i = 0; i < l; i++)
{
for(int j = 1; j <= w; j++)
{
if(!used[i * w + j])
{
dfs1(i * w + j);
}
}
}
for(int i = ord.size() - 1; i >= 0; i--)
{
if(!color[ord[i]])
{
++scccnt;
dfs2(ord[i]);
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> w >> l;
for(int i = 1; i <= l; i++)
{
for(int j = 1; j <= w; j++)
{
cin >> mat[i][j];
}
}
for(int i = 1; i <= l; i++)
{
for(int j = 1; j <= w; j++)
{
two2one(i, j, i + 1, j);
two2one(i, j, i - 1, j);
two2one(i, j, i, j + 1);
two2one(i, j, i, j - 1);
}
}
//求强联通分量
//ord.push_back(0);
cout << Kosaraju();
return 0;
}