CF1385 E

我们发现好像和拓扑序有关
我们做拓扑序的时候 要是一个点没有 有向边出去 或者进来 我们好像可以随意钦定该点其他无向边
要是有 有向边入 和 有向边出 那么肯定寄 有一种就直接钦定为该点其他有向边的方向就可以了
其实 具体实现的时候我们可以直接有向边拓扑序 之后 无向边钦定 由拓扑序小的指向拓扑序大的即可
因为我们会发现上面那个过程是不会钦定为 入的

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;
        }
    }
}