20pts,求空间优化
查看原帖
20pts,求空间优化
816204
Light_LE楼主2024/9/29 23:16

只过了第一个测试点

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define maxn 100003
using namespace std;
int n/*V*/, m, vis[maxn];
vector<int> G[maxn];
queue<int> q;
void dfs(int V) {
	if (V > n) {
		return;
	}
	
	cout << V << " ";
	for (int i = 0; i < G[V].size(); i++) {
		if(vis[G[V][i]] == 0) {
			dfs(G[V][i]);
			vis[G[V][i]] = 1;
		}
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int V, U;
		cin >> V >> U;
		G[V].push_back(U);
	}
	for (int i = 1; i <= n; i++) {
		sort(G[i].begin(), G[i].end());
	}
	
	dfs(1);
	cout << endl;
	
	memset(vis, 0, sizeof(vis));
	q.push(1);
	while (q.size()) {
		int f = q.front();
		q.pop();
		
		if (f > n) {
			continue;
		}
		
		cout << f << " ";
		for (int i = 0; i < G[f].size(); i++) {
			if (vis[G[f][i]] == 0) {
				q.push(G[f][i]);
				vis[G[f][i]] = 1;
			}
		}
	}
	return 0;
}
2024/9/29 23:16
加载中...