【Codeforces 555E】Case of Computer Network | Mrsrz's blog

边双缩点，树上差分

题目大意：

给定一张无向图，有 $q$ 条有向路径。

要求给无向图的每条边定向，并使 $q$ 条路径仍然连通。

问是否存在方案。

题解：

一个边双中的点，两两之间有至少两条路径，必然可达。所以先缩成一个点。

然后就变成一个森林上的问题了。

如果两个点不连通，那么显然不存在。

否则，我们拆成 $u\rightarrow \mathrm{LCA}(u,v)$ 和 $\mathrm{LCA}(u,v)\rightarrow v$ 两条路径。分别在这两条路径上打向上、向下的标记。

如果一条边既有向上有有向下则不可行。不存在则可以。

本题是最后查询，所以可以树上差分得到每条边，向上的链的数量和向下的链的数量。

Code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int N=2e5+5;
int n,m,q,X[N],Y[N],head[N],cnt=1,dfn[N],low[N],idx,sta[N],tp,SCC,bel[N],dep[N],fa[N],top[N],sz[N],son[N];
int siz[N],dad[N];
bool vis[N];
inline int find(int x){while(x!=dad[x])x=dad[x]=dad[dad[x]];return x;}
inline void merge(int u,int v){
    u=find(u),v=find(v);
    if(u==v)return;
    if(siz[u]<siz[v])swap(u,v);
    siz[u]+=siz[v],dad[v]=u;
}
struct edge{
    int to,nxt;
}e[N<<1];
vector<int>G[N];
void DFS(int now,int pre){
    dfn[now]=low[now]=++idx;
    vis[now]=1;
    sta[++tp]=now;
    for(int i=head[now];i;i=e[i].nxt)
    if(i!=pre){
        if(!dfn[e[i].to]){
            DFS(e[i].to,i^1);
            low[now]=min(low[now],low[e[i].to]);
        }else
        if(vis[now])low[now]=min(low[now],dfn[e[i].to]);
    }
    if(low[now]==dfn[now]){
        int v;
        ++SCC;
        do{
            v=sta[tp--];
            bel[v]=SCC;
            vis[v]=0;
        }while(v!=now);
    }
}
void dfs(int now){
    sz[now]=1;
    for(int to:G[now])if(!dep[to]){
        dep[to]=dep[now]+1,fa[to]=now;
        dfs(to);
        sz[now]+=sz[to];
        if(sz[son[now]]<sz[to])son[now]=to;
    }
}
void dfs2(int now){
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int to:G[now])
    if(dep[to]>dep[now]&&to!=son[now])dfs2(top[to]=to);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
void DfS(int now){
    for(int to:G[now])if(dep[to]>dep[now]){
        DfS(to);
        X[now]+=X[to],Y[now]+=Y[to];
    }
    if(X[now]&&Y[now])cout<<"No\n",exit(0);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;++i)dad[i]=i;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
        merge(u,v);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])DFS(i,0);
    for(int u=1;u<=n;++u)
    for(int i=head[u];i;i=e[i].nxt)
    if(bel[u]!=bel[e[i].to])
    G[bel[u]].push_back(bel[e[i].to]);
    for(int i=1;i<=SCC;++i)if(!dep[i])dep[i]=1,dfs(i),dfs2(i);
    while(q--){
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v))cout<<"No\n",exit(0);
        u=bel[u],v=bel[v];
        int w=LCA(u,v);
        ++X[u],++Y[v],--X[w],--Y[w];
    }
    for(int i=1;i<=SCC;++i)if(dep[i]==1)DfS(i);
    cout<<"Yes\n";
    return 0;
}