Skip to content

14180: 【原4180】混合图定向

题目

题目描述

author: Konpaku 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4180

Description

有一张 \(n\) 个点的混合图,编号从 \(1\) 至 \(n\),图中有 \(p_1\) 条有向边和 \(p_2\) 条无向边。
你需要为每条无向边定向,使得图中不存在环。若有多组定向方案,输出任意一组即可。

Input Format

第一行三个整数 \(n\), \(p_1\), \(p_2\) 意义如上。
接下来 \(p_1\) 行,每行两个整数 \(a\) , \(b\) 表示一条由 \(a\) 到 \(b\) 的有向边。
接下来 \(p_2\) 行,每行两个整数 \(a\) , \(b\) 表示一条连接 \(a\) , \(b\) 的无向边。

Output Format

输出包括 \(p_2\) 行,每行两个整数。
第 \(i\) 行的两个整数 \(a_i\) , \(b_i\) 表示对于第 \(i\) 条无向边,其最终方向由 \(a_i\) 指向 \(b_i\)。
请确保输出的有向边与输入的无向边相对应。

Sample Input

4 2 3
1 2
4 3
1 3
4 2
3 2

Sample Output

1 3
4 2
2 3

Data Range

对于20%的数据:\(0<n<=10, 0<p1<=10, 0<p2<=5\)
对于30%的数据:\(0<n<=10, 0<p1<=30, 0<p2<=20\)
对于100%的数据:\(0<n, p1, p2<=100000\)
数据保证至少存在一种可行解

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int to[100005], nxt[100005], at[100005] = {0}, cnt = 0;
int fr[100005], to2[100005];
int dir[100005] = {0}, du[100005] = {0}, rk[100005] = {0};
int n, m1, m2;
queue<int> q;
void init(){
    n = read(), m1 = read(), m2 = read();
    REP(i, 1, m1){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        ++du[v];
    }
    REP(i, 1, m2)
        fr[i] = read(), to2[i] = read();
}
void solve(){
    REP(i, 1, n){
        if (!du[i])
            q.push(i);
    }
    REP(i, 1, n){
        int h = q.front();
        q.pop();
        rk[h] = i;
        for (int i = at[h]; i; i = nxt[i]){
            int v = to[i];
            --du[v];
            if (!du[v]) q.push(v);
        }
    }
    REP(i, 1, m2){
        if (rk[fr[i]] < rk[to2[i]])
            printf("%d %d\n", fr[i], to2[i]);
        else
            printf("%d %d\n", to2[i], fr[i]);
    }
}
int main(){
    init();
    solve();
    return 0;
}