图的遍历()
  • 板块学术版
  • 楼主TARGETMINE
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/5 19:05
  • 上次更新2023/11/2 15:26:15
查看原帖
图的遍历()
935263
TARGETMINE楼主2023/10/5 19:05

https://www.luogu.com.cn/problem/P2921 请问这道题怎么改一下啊(屎山代码,勿喷qwq)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100005;
const int M = 100010;
int isgo[N]; 
int ans = 0;

int h[N], e[M], nex[N], idx=0;

void add(int a,int b)
{
	e[idx] = b;
	nex[idx] = h[a];
	h[a] = idx;
	idx++;
}

void dfs(int head)
{
	isgo[head] = 1;
	
	for (int i=h[head];i!=-1;i = nex[i])
	{
		int j = e[i];
		if(!isgo[j])
		{
			ans++;
			dfs(j);
		}
	}
}


int main()
{
	memset(h, -1, sizeof(h));
	
	int n, next;
	
	cin >> n;
	for (int i=1;i<=n;i++)
	{
		cin >> next;
		add(i, next);
	}
	
	for (int i=1;i<=n;i++)
	{
		ans = 0;
		memset(isgo, 0, sizeof(isgo));
		dfs(i);
		cout << ans+1 << endl;
		
	}
	


	return 0;
}
2023/10/5 19:05
加载中...