这题能不能用二分图做？

AssiduousCoding @ 2024-07-24 11:17:34

by AssiduousCoding @ 2024-07-24 14:41:32

二分图代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1510;

int n;

int head[N], e[N * 2], ne[N * 2], cur;

int color[N];

int cnt = 0;

void add(int a, int b)

{

    e[cur] = b, ne[cur] = head[a], head[a] = cur ++ ;

}

void dfs(int u, int c) 

{

    color[u] = c;

    if (color[u] == 1) cnt ++ ;

    for (int i = head[u]; ~i; i = ne[i])

    {

        int j = e[i];

        if (!color[j]) dfs(j, 3 - c);

    }

}

int main() 

{   

    cin >> n;

    memset(head, -1, sizeof head);

    for (int i = 1; i <= n; i ++ )

    {

        int u, v, t;

        cin >> u >> t;

        while (t -- )

        {

            cin >> v;

            add(u, v), add(v, u);

        }

    }

    dfs(1, 1);

    cout << min(cnt, n - cnt) << endl;

    return 0;

}

by JOKER_chu @ 2024-09-16 22:28:06

@AssiduousCoding 二分图和树就不是一个东西，学懂了再装逼吧

by AssiduousCoding @ 2024-09-19 18:55:40

@JOKER_chu 弱弱地问一下大佬：树能不能看做有向无环图，然后用二分图

by JOKER_chu @ 2024-09-19 19:08:54

@AssiduousCoding 哥们，有向无环图不一定是二分图啊，你这二分图的概念都不懂，代码抄了没用的

by AssiduousCoding @ 2024-09-19 19:13:07

@JOKER_chu 可是树一定是二分图啊？

by JOKER_chu @ 2024-09-19 19:15:29

@AssiduousCoding 您说的不是有向无环图进行染色吗

by JOKER_chu @ 2024-09-19 19:16:40

@AssiduousCoding 就算树是二分图，但是您用手造一组数据都知道不是交替放最优啊

by AssiduousCoding @ 2024-09-19 19:21:39

@JOKER_chu 大佬能提供一下hack数据吗？

by JOKER_chu @ 2024-09-19 20:01:42

@AssiduousCoding 搞不出来，但类似一个满二叉树再加点东西应该就能卡掉了

by DMY555888 @ 2024-09-23 16:25:49

WEDwkuikwhsvkr爱人声卡网卡色二恶热惹惹rereadr而儿