P5318 【深基18.例3】查找文献

基本思路

邻接表实现，结果得为了边有序再专门开一个 vector 预处理完再存边。

而且一开始忘记 vis[1] = true 了！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>

const int N = 1e6 + 10;

int head[N], tot;
int vis[N];
std::vector<int> temp[N];

struct Node {
	int to, next;
}edge[N];

bool cmp(int x, int y) { return x > y; }

void addEdge(int u, int v)
{
	edge[++tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot;
}

int n, m;

void DFS(int now)
{
	std::cout << now << " ";
	for (int i = head[now]; i ; i = edge[i].next)
	{
		if (!vis[edge[i].to])
		{
			vis[edge[i].to] = true;
			DFS(edge[i].to);
		}	
	} 
}

void BFS()
{
	std::cout << std::endl;
	std::queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int now = q.front();q.pop();
		std::cout << now << " ";
		for (int i = head[now]; i ; i = edge[i].next)
		{
			if(!vis[edge[i].to])
			{
				vis[edge[i].to] = true;
				q.push(edge[i].to);
			}
		}
	}
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n >> m;
	for (int i = 1; i <= m; i++) 
	{
		int x, y;
		std::cin >> x >> y;
		temp[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		sort(temp[i].begin(), temp[i].end(), cmp);
	}
	for (int i = 1; i <= n; i++)
	{
		for (auto u : temp[i])
		{
			addEdge(i, u);
		}
	}
	vis[1] = true;
	DFS(1);
	std::memset(vis, 0, sizeof(vis));
	vis[1] = true;
	BFS();
	return 0;
}

邻接矩阵

用 vector 实现的邻接矩阵，显然更自然，毕竟存边完直接排序。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>

const int N = 1e6 + 10;

int vis[N];
std::vector<int> edge[N];

int n, m;

void DFS(int now)
{
	std::cout << now << " ";
	for (auto to : edge[now])
	{
		if (!vis[to])
		{
			vis[to] = true;
			DFS(to);
		}	
	} 
}

void BFS()
{
	std::cout << std::endl;
	std::queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int now = q.front();q.pop();
		std::cout << now << " ";
		for (auto to : edge[now])
		{
			if(!vis[to])
			{
				vis[to] = true;
				q.push(to);
			}
		}
	}
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n >> m;
	for (int i = 1; i <= m; i++) 
	{
		int x, y;
		std::cin >> x >> y;
		edge[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		sort(edge[i].begin(), edge[i].end());
	}
	vis[1] = true;
	DFS(1);
	std::memset(vis, 0, sizeof(vis));
	vis[1] = true;
	BFS();
	return 0;
}