【图论记录】[NEERC2017]Connections

wgyhm · 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;
}