M_sea

洛谷1330 封锁阳光大学
Luogu算法简单的Dfs(或者叫做二分图染色?)。首先对每一个子连通图进行染色,之后统计出染成黑色的数量和染成白...
扫描右侧二维码阅读全文
17
2018/07

洛谷1330 封锁阳光大学

Luogu

算法

简单的Dfs(或者叫做二分图染色?)。

首先对每一个子连通图进行染色,之后统计出染成黑色的数量和染成白色的数量,取最小值加入答案中即可。

在对每一个子图Dfs时,可以顺便统计出子图中的节点数。那么Dfs完后统计出黑色数,用总结点数减黑色数就是白色数。

注意:双向边图不一定联通

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; };
Edge e[500010];
int head[50010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int n,m,sum;
bool vis[50010];
int color[50010];

inline void Dfs(int u,int c) {
    if (color[u]!=-1&&color[u]!=c) { puts("Impossible"); exit(0); }
    if (color[u]==c) return;
    vis[u]=1; color[u]=c; sum++;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        Dfs(v,c^1);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        int a=read(),b=read();
        addEdge(a,b);
        addEdge(b,a);
    }
    int ans=0;
    for (re int i=1;i<=n;i++)
        if (!vis[i]) {
            memset(color,-1,sizeof(color));
            sum=0; Dfs(i,1); int t=0;
            for (re int i=1;i<=n;i++) t+=(color[i]==1);
            ans+=min(t,sum-t);
        }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 55 PM

发表评论