自动搬运

查看原文

来自洛谷，原作者为

	AzzyZhe 誰かの風景を塗り替える それが嬉しかった

搬运于2025-08-24 22:27:53，当前版本为作者最后更新于2021-02-03 19:49:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解 P7228 [COCI2015-2016#3] MOLEKULE

我也来水题解了

思路分析

题目要求我们构造一种方案，确定一个$n$个点$n-1$条边的无向图各边方向，使产生的有向图中的最大连通块最小。很自然会想到树的情况，或者先考虑链的情况，不难得出只要原图上直接相连的点只要满足间隔地所连边都指向指出自己，或者说入度出度间歇地为$0$，就一定能得到为$1$的最小代价。例如：

1->2<-3->4<-5

和

    1<-8
    ^
 2<-3->4<-5
    v     v
    6     7

实现上，我们可以用一次无向图$dfs$解决问题。

从任意图中任一点$p$开始，先假定构造了一个有向图使刚好可以从该点遍历全图，$dfs$过程中将与该点$p$距离为奇数（或偶数）的边标记取反，再结合原边的情况取反即可。

其中最需要注意的是虽然是无向图，但由于最后输出的是是否与给出的边反向，建立无向图时依然需要考虑区分原边和反向边。这里我们选择将反向边存在$MAXN$以后的新区域（这样同时也可以用边的下标判断是不是原边），对于反向边遍历时需要调换方向的边即不需要调换，因此从哪个点开始$dfs$都没问题

代码

#include<iostream>
#define endl '\n'
using namespace std;
#define MAXN 100001
int n;
struct edge{
    int v;
    int next;
}e[MAXN<<1];
int head[MAXN];
bool towards[MAXN];//确认边要不要调换方向
bool f=0;//初始为0或1都没关系
bool vis[MAXN];
void dfs(int p)
{
    if(vis[p])
        return;
    vis[p]=1;
    f^=1;
    for(int i=head[p];i;i=e[i].next)
    {
        if(vis[e[i].v])
            continue;
        //f^=1;
        if(i>MAXN)
            towards[i-MAXN]=f^1;
        else
            towards[i]=f;
        dfs(e[i].v);
        //f^=1;
    }
    f^=1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,j=MAXN+1,u,v;i<n;i++,j++)
    {
        cin>>u>>v;
        e[i].v=v,e[i].next=head[u],head[u]=i;//加边
        e[j].v=u,e[j].next=head[v],head[v]=j;//无向图加反向边  
    }
    dfs(0);
    for(int i=1;i<n;i++)
        cout<<towards[i]<<endl;
    return 0;
}

其他

回到一开始，$n$个点$n-1$条边的图就一定是树吗？实际上，题面中并没有说这个$n$个点$n-1$条边的无向图是连通的（虽然测试点中是这样体现的），也许这个图可能是分别连通的两部分，甚至说不定可能有环和平行边（自环平行边大概一般都不考虑）。所以之前的思考其实是不全面的。

幸运的是，再次考虑我们刚才的思路。只需分别从每个点进行一遍$dfs$（不重置$vis[]$）即可；而对于存在环的部分$dfs$同样适用，只是不能保证奇数个节点的环上最小代价总为$1$；至于平行边的问题在$dfs$同时也可以不需要任何额外步骤就得到解决。

蒟蒻作题解，如有错误欢迎各位大佬指出

小错误是故意的w