1 条题解

  • 0
    @ 2026-5-5 16:31:15
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 200005;
    int n, m, q, x, y, id, cnt, dfn[N], low[N], f[N], a[N], b[N], c[N], bl[N];
    vector<int> e[N], w[N], E[N];
    vector<pair<int,int>> s;
    void add(vector<int> *e, int x, int y){ e[x].push_back(y), e[y].push_back(x);}
    void dfs2(int u){ bl[u]=id; for(int v:e[u]) if(v && !bl[v]) dfs2(v);}
    void dfs(int u, int fa=0){
    	dfn[u]=low[u]=++cnt;
    	for(int &v:e[u]) if(v!=fa){
    		if(!dfn[v]){
    			dfs(v, u), low[u]=min(low[u], low[v]);
    			if(low[v]==dfn[v]) s.emplace_back(u, v), v=0;
    		}
    		else low[u]=min(low[u], dfn[v]);
    	}
    	else v=fa=0;
    	if(low[u]==dfn[u]) ++id, dfs2(u);
    }
    int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}
    void dfs3(int u, int fa=0){
    	for(int v:E[u]) if(v!=fa)
    		dfs3(v, u), f[v]=u, a[u]+=a[v], b[u]+=b[v], c[u]+=c[v];
    	for(int v:w[u]) if(v!=f[v]) ++c[find(v)];
    	if(a[u]>c[u] && b[u]>c[u]) puts("No"), exit(0);
    }
    int main() {
    	scanf("%d%d%d", &n, &m, &q);
    	for(int i=1; i<=m; ++i) scanf("%d%d", &x, &y), add(e, x, y);
    	for(int i=1; i<=n; f[i]=i, ++i) if(!dfn[i]) dfs(i);
    	for(auto i:s) add(E, x=bl[i.first], y=bl[i.second]), f[find(x)]=find(y);
    	for(int i=1; i<=q; ++i){
    		scanf("%d%d", &x, &y);
    		if((x=bl[x])!=(y=bl[y])) ++a[x], ++b[y], add(w, x, y);
    		if(find(x)!=find(y)) return puts("No"), 0;
    	}
    	for(int i=1; i<=id; ++i) f[i]=i;
    	for(int i=1; i<=id; ++i) if(i==f[i]) dfs3(i);
    	return puts("Yes"), 0;
    }
    
    • 1

    信息

    ID
    6870
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者