自动搬运

查看原文

来自洛谷，原作者为

	wgyhm CF不上GM不改

搬运于2025-08-24 22:25:26，当前版本为作者最后更新于2021-12-26 15:18:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[NEERC2017]Connections

Description

给定一个 $n$ 点有向图，要求保留 $2n$ 条边使得强连通关系不变，输出删去的边。多测。

Solution

先把强连通分量用 tarjan 跑出来。

• 连接两个强连通分量的不需要保留
• 对于其他的边，在一个强连通分量内部随便找个点 $x$，只要每个点与 $x$ 联通，那么其它点就可以经过 $x$ 到达所有点。所以只要对于 $x$ 分别跑个内向树和外向树，树边保留。
• 如果还没满 $2*n$ ，那么随便选几条就好。

多测不清空，$\_\_\_\_\_\_$。

code:

#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,m;
int stac[maxn],vis[maxn],scc[maxn],sccnum,tot,times;
int dfn[maxn],low[maxn],head=1,h[maxn],hh[maxn];
struct yyy{
	int to,z;
	inline void add(int x,int y){
		to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
struct node{
	int to,z;
	inline void add(int x,int y){
		to=y;z=hh[x];hh[x]=head;
	}
}e[maxn*2];
inline void tarjan(int x) {
	int i;
	vis[x]=1;dfn[x]=low[x]=++times;stac[++tot]=x;
    for (i=h[x];i;i=a[i].z) 
        if (!dfn[a[i].to]) tarjan(a[i].to),low[x]=min(low[a[i].to],low[x]);
		else if (vis[a[i].to]) low[x]=min(low[x],dfn[a[i].to]);
	if (low[x]==dfn[x]) {
		++sccnum;
		while (1) {
			vis[stac[tot]]=0;
			scc[stac[tot]]=sccnum;
			if (stac[tot--]==x) return; 
		}
	}
}
int flag[maxn];
inline void dfs1(int x) {
	int i;vis[x]=1;
	for (i=h[x];i;i=a[i].z)
	    if (!vis[a[i].to]&&scc[a[i].to]==scc[x]) 
	        flag[i]=1,dfs1(a[i].to);
}
inline void dfs2(int x) {
	int i;vis[x]=1;
	for (i=hh[x];i;i=e[i].z)
	    if (!vis[e[i].to]&&scc[e[i].to]==scc[x]) 
	        flag[i]=1,dfs2(e[i].to);
}
inline void solve(void) {
	int i,x,y;
    read(n);read(m);
    sccnum=times=0;head=0;
    for (i=1;i<=n;i++) {
    	h[i]=hh[i]=dfn[i]=stac[i]=low[i]=scc[i]=vis[i]=0;
	}
	for (i=1;i<=m;i++) flag[i]=0;
    for (i=1;i<=m;i++) {
    	read(x);read(y);
    	a[++head].add(x,y);
    	e[head].add(y,x);
	}
	for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
	for (i=1;i<=n;i++) vis[i]=0;
	for (i=1;i<=n;i++) if (!vis[i]) dfs1(i);
	for (i=1;i<=n;i++) vis[i]=0;
	for (i=1;i<=n;i++) if (!vis[i]) dfs2(i);
	int total=0;
	for (i=1;i<=m;i++) total+=flag[i];
	for (i=1;i<=m;i++)
	    if (flag[i]) ;
	    else if (total<2*n) total++;
	    else printf("%d %d\n",e[i].to,a[i].to);
}
signed main(void){
    int T;
    read(T);
    while (T--) solve();
	return 0;
}