T189317

Aryper · 2021-07-26 12:30:32 · 个人记录

B. 有向图【NOIP 计划 · 模拟赛 #1】

构造题。

然后我们知道边数为奇数时不存在方案，偶数时一定存在。当作是出度分配给 m 条边，然后出度的总和一定是偶数，所以边数不能为奇数。。。

解释不清。。接着我们可以找出图中的 dfs 树，给返祖边随意分配方向，接着从叶节点开始决定其到父节点的方向即可。

主要是要证最后到根节点的时候根节点的出度一定为偶数。因为其他节点都可以根据情况改变与父节点的连边方向使出度为偶，只有根节点不行。

我们已经知道除了根节点之外所有点的出度均为偶数了，那么很显然总出度也是偶数，最后留给根节点的出度自然也是偶数。证毕。

时间复杂度 O(m) 。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,m,u,v,flg,tot;

ll ver[N*2+5],nxt[N*2+5],head[N+5],vis[N+5],cnt[N+5],dep[N+5];

void dfs(ll p,ll fath) {
    vis[p]=1;dep[p]=dep[fath]+1;
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath) continue;
        if(vis[ver[i]]) {
            if(dep[p]>dep[ver[i]]) {
                cnt[p]++;
                printf("%lld %lld\n",p,ver[i]);
            }
        }
        else dfs(ver[i],p);
    }
    if(cnt[p]%2==1) {
        cnt[p]++;printf("%lld %lld\n",p,fath);
    }
    else {
        if(fath!=0) {
            cnt[fath]++;printf("%lld %lld\n",fath,p);
        }
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        add(u,v);add(v,u);
    }

    if(m%2==1) flg=1;

    if(flg==0) {

        dfs(1,0);

    }
    else {
        printf("-1\n");
    }

    return 0;
}