Codeforces542E Playing on Graph 思维+DFS+BFS

解法参考https://www.cnblogs.com/BearChild/p/7683114.html这位大佬的，这位大佬讲得很好了。

这道题还是有一定的思维的。

直接贴代码：

#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

#include<cstring>

using namespace std;

const int N=+;

const int M=+;

int n,m,ecc_cnt,ans,color[N],Max[N],ecc[N];

vector<int> G[N];

bool ok;

void dfs(int x,int c) {

    color[x]=c; ecc[x]=ecc_cnt;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        if (color[y]==color[x]) ok=false;

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

    }

}

queue<int> q;

int d[N];

int bfs(int s) {

    while (!q.empty()) q.pop();

    memset(d,,sizeof(d));

    d[s]=; q.push(s);

    int res=;

    while (!q.empty()) {

        int x=q.front(); q.pop();

        for (int i=;i<G[x].size();i++) {

            int y=G[x][i];

            if (!d[y]) {

                d[y]=d[x]+;

                res=max(res,d[y]);

                q.push(y);

            }

        }

    }

    return res;

}

int main()

{

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

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

        int x,y; scanf("%d%d",&x,&y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    ecc_cnt=; ok=true;

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

        if (!ecc[i]) {

            ecc_cnt++;

            dfs(i,);

        }

    if (!ok) { puts("-1"); return ; }

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

        Max[ecc[i]]=max(Max[ecc[i]],bfs(i));

    for (int i=;i<=ecc_cnt;i++) ans+=Max[i]-;

    cout<<ans;

    return ;

}