我们发现好像和拓扑序有关
我们做拓扑序的时候 要是一个点没有 有向边出去 或者进来 我们好像可以随意钦定该点其他无向边
要是有 有向边入 和 有向边出 那么肯定寄 有一种就直接钦定为该点其他有向边的方向就可以了
其实 具体实现的时候我们可以直接有向边拓扑序 之后 无向边钦定 由拓扑序小的指向拓扑序大的即可
因为我们会发现上面那个过程是不会钦定为 入的
void solve(){
int n,m;cin>>n>>m;
vector<PII>g[n+1];
vector<int>deg(n+1),in(n+1);
vector<PII>ans;
for(int i=1;i<=m;i++){
int t,u,v;cin>>t>>u>>v;
if(!t){
g[u].push_back({v,0});
g[v].push_back({u,0});
deg[u]++;
deg[v]++;
}else{
g[u].push_back({v,1});
ans.push_back({u,v});
deg[v]++;
in[v]++;
}
}
queue<int>q;
vector<int>st(n+1);
set<PII>c;
for(int i=1;i<=n;i++)if(!deg[i]||!in[i])q.push(i),st[i]=1;
while(q.size()){
auto u=q.front();q.pop();
for(auto [v,t]:g[u]){
if(!t&&c.count({u,v})==0&&c.count({v,u})==0){
deg[v]--;
deg[u]--;
if(!in[u])ans.push_back({u,v}),c.insert({u,v});
}
if(!deg[v]||!in[v])if(!st[v])q.push(v),st[v]=1;
}
for(auto [v,t]:g[u]){
if(t){
deg[v]--;
in[v]--;
}
if(!deg[v]||!in[v])if(!st[v])q.push(v),st[v]=1;
}
}
if(ans.size()!=m){
NO
}else{
vector<int>ng[n+1],deg(n+1);
for(auto [u,v]:ans){
ng[u].push_back(v);
deg[v]++;
}
queue<int>q;
for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
while(q.size()){
auto u=q.front();q.pop();
for(auto v:ng[u]){
deg[v]--;
if(!deg[v])q.push(v);
}
}
for(int i=1;i<=n;i++)if(deg[i]>0) {
NO return;
}
YES
for(auto [u,v]:ans){
cout<<u<<' '<<v<<endl;
}
}
}