请教一下使用反向建边并深搜的代码的错误
查看原帖
请教一下使用反向建边并深搜的代码的错误
576807
URbit楼主2022/12/11 15:12

如题,WA后五点

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

struct Edge
{
	int ver;
	Edge* next;

	Edge(int v) :ver(v), next(nullptr) {}
};

struct Vertex
{
	int ver = 0;
	int cow = 0;
	int come = 0;

	Edge* link = nullptr;
} pastures[1010];

int K, N, M;
int ans = 0;
int vis[1010];

void dfs(int x, int cow)
{
	vis[x] = 1;
	pastures[x].come += cow;
	for (Edge* p = pastures[x].link; p; p = p->next)
	{
		if (vis[p->ver] == 0)
			dfs(p->ver, cow);
	}
}

int main()
{
	cin >> K >> N >> M;
	for (int i = 1; i <= N; i++)
		pastures[i].ver = i;
	for (int i = 1; i <= K; i++)
	{
		int x;
		cin >> x;
		pastures[x].cow++;
	}
	for (int i = 1; i <= M; i++)
	{
		int x, y;
		cin >> x >> y;
		Edge* temp = new Edge(x);
		temp->next = pastures[y].link;
		pastures[y].link = temp;
	}

	for (int j = 1; j <= N; j++)
	{
		if (pastures[j].cow > 0)
		{
			for (int i = 1; i <= N; i++)
				vis[i] = 0;
			dfs(j, pastures[j].cow);
		}
	}
	for (int i = 1; i <= N; i++)
		if (pastures[i].come == K) ans++;
	cout << ans;
	return 0;
}
2022/12/11 15:12
加载中...