Dizzy Cows (토폴로지)

링크:https://ac.nowcoder.com/acm/contest/1077/D 우 객 망
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 32768 K, 기타 언어 65536 K Special Judge, 64bit IO Format:% lld 제목 설명 소 는 농장 주변 에서 서로 경주 하기 위해 촬영 했 지만 원 에서 실행 할 때 매우 어 지 럽 습 니 다. and everyone knows that dizzy cows don’t produce any milk. Farmer John wants to convert all of the two-way cow paths in the farm to one-way paths in order to eliminate any ‘cycles’ and prevent the cows from getting dizzy. A ‘cycle’ enables a cow to traverse one or more cow paths and arrive back at her starting point, thus completing a loop or circle. The farm comprises N pastures (1 <= N <= 100,000) conveniently numbered 1…N. M1 (1 <= M1 <= 100,000) one-way cow paths and M2 two-way cow paths (1 <= M2 <= 100,000) connect the pastures. No path directly connects a pasture to itself, although multiple paths might connect two different pastures. A cow may or may not be able to travel between any two given pastures by following a sequence of cow paths. Your job is to assign a direction to the two-way cow paths such that the entire farm (ultimately with only one-way paths) has no cycles. That is, there should be no sequence of one-way cow paths which leads back to its starting position. The existing one-way cow paths do not form a cycle and should be left as they are. One-way cow paths run from pasture Ai (1 <= Ai <= N) to pasture Bi (1 <= Bi <= N). Two-way cow paths connect pastures Xi (1 <= Xi <= N) and Yi (1 <= Yi <= N). Consider this example:

             1-->2
             |  /|
             | / |
             |/  |
             3

The cow paths between pastures 1 and 3, 2 and 3, and 2 and 4 are two-way paths. One-way paths connect 1 to 2 and also 4 to 3. One valid way to convert the two-way paths into one-way paths in such a way that there are no cycles would be to direct them from 1 to 3, from 2 to 3, and from 3 to 4:

         1-->2
         |  /|
         | / |
         vL  v
         3

입력 설명:

Line 1: Three space separated integers: N, M1, and M2

Lines 2…1+M1: Line i+1 describes a one-way cow path using two space separated integers: Ai and Bi

Lines 2 + M1... 1 + M1 + M2: Line i + M1 + 1 은 두 공간 으로 구 분 된 정 수 를 사용 하여 양 방향 암소 경 로 를 설명 합 니 다. Xi 와 Yi 출력 설명:

줄 1... M2: 줄 i 는 i - th 양 방향 경로 에 할 당 된 방향 에 따라 Xi 와 Yi 또는 Yi 와 Xi 중 두 개의 공간 으로 분 리 된 정 수 를 포함해 야 합 니 다. 양 방향 경 로 는 입력 에서 와 같은 순서 로 출력 에 나타 나 야 합 니 다. 솔 루 션 이 없 으 면 단일 줄 에서 "- 1" 을 출력 합 니 다. 예제 1 입력 복사

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

출력 복사

1 3
4 2
2 3

/ * 제목 은 그림 이 링 을 구성 하지 않도록 방향 을 표시 하지 않 는 다 는 것 이다.링 을 구성 하지 않 으 면 토폴로지 정렬 을 생각 하기 쉽다.
대응 코드 2: 처음에 저 는 가입 을 했 기 때문에 토폴로지 정렬 을 했 습 니 다 (방향 이 없 는 도 는 아 닙 니 다). 대기 열 에서 나 온 이 점 이 방향 이 없 는 변 과 연결 되 었 을 때 출력: 현재 점 – > 방향 이 없 는 변 을 통 해 연 결 된 점 을 표시 하 는 방법 은 모 르 겠 습 니 다. 출력 된 방향 이 없 는 변 (즉 방향 이 확 정 된 변) 은 방향 을 정 했 습 니 다.표시 되 지 않 은 화 는 역방향 변 을 다시 출력 합 니 다.(나중에 어리숙 하 게 나타 난 것 은 실질 적 으로 역방향 표시 문제 이다. 이 변 의 역방향 표 시 를 빨리 찾 고 표 시 를 사용 할 수 없다).어떻게 한 변 의 반대 변 을 빨리 찾 습 니까?(각 변 은 이미 레이 블 이 표시 되 어 있 고 방향 변 레이 블 이 인접 해 있다):
nowID ^ 1 은 반대 쪽 번호 입 니 다.
대응 코드 1: 반대 쪽 을 표시 하지 않 으 면 생각 을 바 꿔 야 합 니 다. 가장자리 에 있 는 점 에 대해 토폴로지 정렬 을 하고 각 점 의 등장 순서 (토폴로지 순서) 를 기록 하여 토폴로지 순서 가 작은 방향 으로 큰 것 을 가리 키 면 ok 입 니 다.
* / 코드 1:

#include 
using namespace std;
const int N = 1e5+5;
struct Edge
{
    int to;
    int val;
    int nxt;
} edge[N<<1];
int head[N],idx,top[N];
int in[N];
int n,m1,m2;
void add_edge(int from,int to,int val)
{
    edge[idx].to = to;
    edge[idx].val = val;
    edge[idx].nxt = head[from];
    head[from] = idx++;
    in[to]++;
}

void topSort()
{
    queue<int>q;
    int tp = 0;
    for(int i = 1; i <= n ; i++)
    {
        if(!in[i])
        {
            q.push(i);
            top[i] = ++tp;
        }
    }
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = head[k]; ~i; i = edge[i].nxt)
        {
            int t = edge[i].to;
            if(!(--in[t]))
            {
                q.push(t);
                top[t] = ++tp;
            }
        }
    }
}
int main()
{
    cin>>n>>m1>>m2;
    int x,y;
    memset(head,-1,sizeof(head));
    for(int i = 0; i < m1; i++)
    {
        cin>>x>>y;
        add_edge(x,y,1);
    }
    topSort();
    for(int i = 0; i < m2; i++)
    {
        cin>>x>>y;
        if(top[x] < top[y])
            cout<<x<<" "<<y<<endl;
        else
            cout<<y<<" "<<x<<endl;
    }
    return 0;
}

코드 2:
/ / 방향 이 정 해 지지 않 은 방향 을 표시 하 는 역방향 변

#include 
using namespace std;
const int N = 1e5+5;
int n,m1,m2,idx;
struct Edge
{
    int from;
    int to;
    int val;
    int nxt;
} edge[N<<1];
int head[N],in[N];
//head[i] i              （           ）
inline void add_edge(int from,int to,int val)
{
    edge[idx].from = from;
    edge[idx].to = to;
    edge[idx].val = val;
    edge[idx].nxt = head[from];
    head[from] = idx++;
}
void topSort()
{
    queue<int>q;
    for(int i = 1; i <= n; i++)
    {
        if(!(in[i])) q.push(i);
    }
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = head[k]; ~i; i = edge[i].nxt)
        {
            if(edge[i].val == 1)
            {
                int t = edge[i].to;
                if(!(--in[t])) q.push(t);
            }
            else if (edge[i].val == 2)
            {
                //cout<
                edge[i^1].val = -1;
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m1>>m2;
    int x,y;
    for(int i = 0; i < m1; i++)
    {
        cin>>x>>y;
        add_edge(x,y,1);
        in[y]++;
    }
    /*
        0  ，
                 ，
       idx    ！！
               ，
                     ，
               。
          ，       。
    */
    if(idx&1) idx++;
    for(int i = 0; i < m2; i++)
    {
        cin>>x>>y;
        add_edge(x,y,2);
        add_edge(y,x,2);
    }
    topSort();
    for(int i = 0; i < idx; i++)
    {
        if(edge[i].val == 2)
            cout<<edge[i].from<<" "<<edge[i].to<<endl;
    }
    return 0;
}