wa&re求助
查看原帖
wa&re求助
723466
banned_gutongxing楼主2023/7/13 19:42

我WAWA了一个点又RERE三个点

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define top front
const int X = 1e5+100;
int n,m,x,y,cnt,h[X],r[X],root;
bool vis[X];
struct node{int to,next;}a[X];
void merge(int x,int y){
	cnt++;
	a[cnt].to = y;
	a[cnt].next = h[x];
	h[x] = cnt;
}
void dfs(int root){
	cout << root << " ";
	vis[root] = 1;
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i = h[root];i;i = a[i].next){
		if(!vis[a[i].to]){q.push(a[i].to);}
	}
	while(!q.empty()){dfs(q.top());q.pop();}
}
void bfs(int root){
	queue<int> q;
	q.push(root);
	while(!q.empty()){
		int tmp = q.front();
		q.pop();
		if(vis[tmp]) continue;
		cout << tmp << " ";
		vis[tmp] = 1;
		priority_queue<int,vector<int>,greater<int> > p;
		for(int i = h[tmp];i;i = a[i].next){
			if(!vis[a[i].to]){
				p.push(a[i].to);
			} 
		}
		while(!p.empty()){
			q.push(p.top());
			p.pop();
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i<=m;i++){
		cin >> x >> y;
		merge(x,y);
		r[y] ++;
	}
	for(int i = 1;i<=n;i++){if(!r[i]){root = i;break;}}
	dfs(root);cout << endl;
	memset(vis,0,sizeof(vis));bfs(root);
	return 0;
}
2023/7/13 19:42
加载中...