Codeforces - 1176E - Cover it!

https://codeforc.es/contest/1176/problem/E

久了不写bfs了。一开始用dfs写，的确用dfs是很有问题的，一些奇怪的情况就会导致多染一些色。

注意无向图的边要开双倍。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;

struct Edge {

    int u, v;

    int next;

    Edge() {}

    Edge(int u, int v, int next): u(u), v(v), next(next) {}

};

struct Graph {

    Edge edge[400005];

    int head[200005], etop;

    void init(int n) {

        etop = 0;

        memset(head + 1, -1, sizeof(head[1])*n);

    }

    void add_edge(int u, int v) {

        edge[++etop] = Edge(u, v, head[u]);

        head[u] = etop;

        edge[++etop] = Edge(v, u, head[v]);

        head[v] = etop;

    }

} g;

bool visited[200005];

bool color[200005];

int dis[200005];

int que[200005];

int qhead, qtail;

int cntodd, cnteven;

void enqueue(int id, int d) {

    if(visited[id])

        return;

    visited[id] = true;

    dis[id] = d;

    if(d & 1)

        cntodd++;

    else

        cnteven++;

    que[++qtail] = id;

}

void bfs() {

    memset(visited + 1, false, sizeof(visited[1])*n);

    qhead = 1, qtail = 0;

    cntodd = 0, cnteven = 0;

    enqueue(1, 0);

    while(qhead <= qtail) {

        int u = que[qhead++];

        for(int i = g.head[u]; i != -1; i = g.edge[i].next) {

            enqueue(g.edge[i].v,dis[u]+1);

        }

    }

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

    //freopen("Yinku.out", "w", stdout);

#endif // Yinku

    int t;

    while(~scanf("%d", &t)) {

        while(t--) {

            scanf("%d%d", &n, &m);

            g.init(n);

            for(int i = 1; i <= m; i++) {

                int u, v;

                scanf("%d%d", &u, &v);

                g.add_edge(u, v);

            }

            bfs();

            int ch = 0;

            if(cntodd <= cnteven)

                ch = 1;

            int cnt = 0, last = -1;

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

                if((dis[i] & 1) == ch) {

                    cnt++;

                    last = i;

                }

            }

            printf("%d\n", cnt);

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

                if((dis[i] & 1) == ch) {

                    printf("%d", i);

                    if(i == last) {

                        printf("\n");

                        break;

                    } else {

                        printf(" ");

                    }

                }

            }

        }

    }

}

巴特西

Codeforces - 1176E - Cover it! - bfs

最新文章

热门文章