RE求助
查看原帖
RE求助
1093247
s1mp1ng楼主2024/1/15 17:03

用的是 KosarajuKosaraju 会有问题吗?

#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;
}
2024/1/15 17:03
加载中...