P1330 封锁阳光大学题解

题目描述

理解：

0x01

此题不就是二分图染色吗?交一个！(备用)😼

啥?40分？不可能！😮
下载数据后，发现:

啥？不是联通图？你不早说 好像的确没说联通欸😅

于是，并查集判联通！ (备用)😼

啥?50分？不可能！😮

0x02

原来是并查集没写好😭

突然想起，我要并查集干嘛？😂

思路

链式前向星存图，使用经典的dfs对每个联通子图进行二分图染色(起点随便染，每个节点染反色，若走了回头路并且颜色不相同，就是非二分图)，统计black,white节点数，取min(black,white)相加即为答案。
参见代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<string>
#include<algorithm>
using namespace std;
struct edge
{
    int to;
    int next;
}e[200000];
int head[20000];
int cnt,black,white;
void add(int a, int b)
{
    cnt++;
    e[cnt].to = b;
    e[cnt].next = head[a];
    head[a] = cnt;
}
bool used[20000];
int col[20000];
bool dfs(int node, int color)
{
    if (used[node])return (col[node] == color);
    used[node] = true;
    col[node] = color;
    if (color) white++; else black++;
    for (int i = head[node]; i; i = e[i].next)
    {
        if(!dfs(e[i].to, 1 - color))return 0;
    }
    return 1;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int a, b;
    while (m--)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (used[i])continue;
        black = white = 0;
        if (!dfs(i, 0))
        {
            printf("Impossible");
            return 0;
        }
        ans += min(black, white);
    }
    printf("%d", ans);
    return 0;
}

下载1 下载2

（不懂Tg问我）