CF 1385E

문제링크

링크텍스트

문제 읽고 드는 생각

일단 n개의 vertices 와 m개의 edges가 있는데 t는 testcase 수 당연히 독립적이고 문제를 읽어보면 연결이 안될 수도 있다고 했다. 자신이 x->x 이런 cycle은 없고 $X_i->Y_i$ , $Y_i->X_i$ 중복은 없다. TestCase를 살펴보면서 일단 방향과 무방향 그래프를 따로 나눠서 관리해야겠다고 생각했고 답의 출력방식은 (in any order)임으로 뭐 어떻게든 구해서 출력하면 되겠다고 생각했다. 그래서 일단 방향그래프끼리 cycle이 있다면 그거는 NO이기 때문이다. 근데 방향 그래프에서 cycle을 구하는 방법이 직접 dfs해서 구하는 법이 있고 위상정렬로 처리한 node개수로 구하는 법이 있다. 근데 보니깐 dfs돌려버리면 $O(N^2)$ 나와서 위상정렬로 처리한 node수를 보고. 구하는 방식을 사용했다. 또 연결이 안된 vertices가 있어서 위상정렬로 처리하는게 좋다고 생각했다. 방향 Edge를 처리한 후. 무방향 Edge를 처리하는 방식으로 갔다.
처음에 틀려가지고 봤더니 NO하고 방향 edge, 무방향 edge Vector를 clear를 안했다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <limits>
#include <sstream>
#include <iomanip>

#define INF 0x3f3f3f3f // 경우에 따라 다르게
// long long 일 1e18

using namespace std;

int t;
int n, m;
// vector<int> edge[200001];
// vector<tuple<int, int, int>> dedge;
vector<int> edge[200001];
// vector<int> unedge[200001];
vector<pair<int, int>> undedge;
int cnt[200001];
int pos[200001];

void sol()
{

    queue<int> q;
    int pn = 1;
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i] == 0)
        {
            q.push(i);
        }
    }

    // 그래프
    vector<pair<int, int>> result;
    int ncnt = 0; // 사이클인가? 과연

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        ncnt++;
        pos[cur] = pn;
        pn++;

        for (auto nxt : edge[cur])
        {
            cnt[nxt]--;
            if (cnt[nxt] == 0)
            {
                q.push(nxt);
                // result.push_back({cur, nxt});
            }
        }
    }

    // cycle 생기는지 확인
    // n * n 번 탐색?

    if (ncnt < n)
    {
        // 방향 그래프끼리 cycle NO

        for (int i = 1; i <= n; i++)
            edge[i].clear();
        undedge.clear();
        cout << "NO" << "\n";
        return;
    }

    // 무방향 연결시켜서

    // 무방향에대해서 무조건 두개의 node가 연결된다면 먼저 처리한 순서 에서
    // 나중 처리한 순서로 연결하면 사이틀 발생 안함

    for (auto E : undedge)
    {
        int x = E.first;
        int y = E.second;
        if (pos[x] < pos[y])
        {
            result.push_back({x, y});
        }
        else
        {
            result.push_back({y, x});
        }
    }

    cout << "YES" << "\n";
    for (auto ans : result)
    {
        cout << ans.first << " " << ans.second << "\n";
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto x : edge[i])
        {
            cout << i << " " << x << "\n";
        }
    }

    for (int i = 1; i <= n; i++)
        edge[i].clear();
    undedge.clear();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t > 0)
    {
        cin >> n >> m;
        fill(cnt, cnt + n + 1, 0);
        fill(pos, pos + n + 1, 0);
        for (int i = 0; i < m; i++)
        {
            int a, x, y;
            cin >> a >> x >> y;
            if (a == 0)
            {
                // unedge[x].push_back(y);
                // unedge[y].push_back(x);
                undedge.push_back({x, y});
            }
            else
            {
                edge[x].push_back(y);
                cnt[y]++;
                // edge.push_back({1, x, y});
            }
        }

        // 만약 direct edge가 없을 때
        sol();

        t--;
    }
}

후기

어려운데 생각을 잘 해야함