2018-ACetic_ACid/AugTrain-11/C

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
vector<int> G[N];
vector<int> H[N];
bool vis[N];
set<pair<int, int> > used;

int main()
{
    int ca;
    scanf("%d", &ca);
    while (ca--)
    {
        used.clear();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            G[i].clear();
            H[i].clear();
            vis[i] = false;
        }
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            H[y].push_back(x);
        }
        queue<int> q;

        int s = 1;
        while (G[s].size() == 0 || H[s].size() == 0)
        {
            s = rand() % n;
        }

        q.push(s);
        vis[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto x:G[u])
            {
                if (!vis[x])
                {
                    used.insert({ u, x });
                    vis[x] = true;
                    q.push(x);
                }
            }
        }

        for (int i = 1; i <= n; i++)
        {
            vis[i] = false;
        }
        q.push(s);
        vis[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto x:H[u])
            {
                if (!vis[x])
                {
                    used.insert({ x, u });
                    vis[x] = true;
                    q.push(x);
                }
            }
        }

        int tot = m - 2 * n;
        int cnt = 0;
        for (int i = 1; cnt < tot && i <= n; i++)
        {
            for (auto x:G[i])
            {
                if (!used.count({ i, x }))
                {
                    printf("%d %d\n", i, x);
                    cnt++;
                }
                if (cnt == tot)
                {
                    break;
                }
            }
        }
    }
}
}}}

#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
vector<int> G[N];
vector<int> H[N];
bool vis[N];
set<pair<int, int> > used;
int main()
{
    int ca;
    scanf("%d", &ca);
    while (ca--)
    {
        used.clear();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            G[i].clear();
            H[i].clear();
            vis[i] = false;
        }
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            H[y].push_back(x);
        }
        queue<int> q;
        int s = 1;
        while (G[s].size() == 0 || H[s].size() == 0)
        {
            s = rand() % n;
        }
        q.push(s);
        vis[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto x:G[u])
            {
                if (!vis[x])
                {
                    used.insert({ u, x });
                    vis[x] = true;
                    q.push(x);
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            vis[i] = false;
        }
        q.push(s);
        vis[s] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto x:H[u])
            {
                if (!vis[x])
                {
                    used.insert({ x, u });
                    vis[x] = true;
                    q.push(x);
                }
            }
        }
        int tot = m - 2 * n;
        int cnt = 0;
        for (int i = 1; cnt < tot && i <= n; i++)
        {
            for (auto x:G[i])
            {
                if (!used.count({ i, x }))
                {
                    printf("%d %d\n", i, x);
                    cnt++;
                }
                if (cnt == tot)
                {
                    break;
                }
            }
        }
    }
}