WA on tes t2求调(玄关)
查看原帖
WA on tes t2求调(玄关)
1026012
fsp_luogu楼主2025/2/5 13:43
#include<iostream>
#include<vector>

using namespace std;

const int N = 2e5 + 10; 

struct Edge{
	int t, u, v;
};

int T, n, m;
Edge edge[N];
int id[N], deg[N];
int q[N], head, tail;
vector<int> e[N];

bool topo(){
	head = 1, tail = 0;
	
	for(int i = 1; i <= n; i ++){
		if(deg[i] == 0){
			q[++tail] = i;
		}
	}
	while(head <= tail){
		int u = q[head];
		head++;
		for(auto v : e[u]){
			deg[v]--;
			if(deg[v] == 0)	q[++tail] = v; 
		}
	}
	if(tail == n){
		for(int i = 1; i <= n; i ++){
			id[q[i]] = i;
		}
		return 1;
	}else{
		return 0;
	}
}

int main(){
	cin >> T;
	while(T--){
		for(int i = 1; i <= n; i ++) e[i].clear();
		cin >> n >> m;
		for(int i = 1; i <= m; i ++){
			cin >> edge[i].t >> edge[i].u >> edge[i].v;
			if(edge[i].t == 1){
				e[edge[i].u].push_back(edge[i].v);
				deg[edge[i].v]++;
			}
				
		}
		if(topo() == 0){
			printf("NO\n");
		}else{
			printf("YES\n");
			for(int i = 1; i <= m; i ++){
				int t = edge[i].t, u = edge[i].u, v = edge[i].v;
				if(t == 1){
					printf("%d %d\n", u, v);
				}else{
					if(id[u] > id[v]) swap(u, v);
					printf("%d %d\n", u, v);
				}
			}
		}
	}
	return 0;
}
2025/2/5 13:43
加载中...