Gym-101630C：Connections（生成树&构造）

题意：给定N点，M条有向边，满足任意点可以到达任意点。现在叫你保留2*N边，任然满足任意点可以到达任意点，输出删除的边。

思路：从1出发，DFS，得到一颗生成树，有N-1条边。反向建题。还是从1出发，得到一颗生成树，这2N-2条边显然可以满足任意点互通。然后随便选两边即可。 （任意点u->v，至少有u->1->v满足。

#include<bits/stdc++.h>

#define pii pair<int,int>

#define ll long long

const int maxn=;

using namespace std;

int u[maxn],v[maxn],vis1[maxn],vis2[maxn],N;

vector<int>G1[maxn],G2[maxn];

map<pii,int>mp;

void dfs1(int u)

{

    vis1[u]=; int L=G1[u].size();

    for(int i=;i<L;i++) if(!vis1[G1[u][i]]) mp[make_pair(u,G1[u][i])]=,dfs1(G1[u][i]);

}

void dfs2(int u)

{

    vis2[u]=; int L=G2[u].size();

    for(int i=;i<L;i++) if(!vis2[G2[u][i]]) mp[make_pair(G2[u][i],u)]=,dfs2(G2[u][i]);

}

int main()

{

    int T,M,i,j;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        mp.clear(); memset(vis1,,sizeof(vis1)); memset(vis2,,sizeof(vis2));

        for(i=;i<=N;i++) G1[i].clear(),G2[i].clear();

        for(i=;i<=M;i++){

            scanf("%d%d",&u[i],&v[i]);

            G1[u[i]].push_back(v[i]);

            G2[v[i]].push_back(u[i]);

        }

        dfs1(); dfs2();

        int cnt=M-N-N;

        for(i=;i<=M&&cnt;i++){

           if(!mp[make_pair(u[i],v[i])]) printf("%d %d\n",u[i],v[i]),cnt--;

        }

    }

    return ;

}