[CSP-S模拟测试]:简单的操作（二分图+图的直径）

题目描述

从前有个包含$n$个点，$m$条边，无自环和重边的无向图。
对于两个没有直接连边的点$u,v$，你可以将它们合并。具体来说，你可以删除$u,v$及所有以它们作为端点的边，然后加入一个新点$x$，将它与所有在原图中与u或v有直接连边的点连边。
你需要判断是否能通过若干次合并操作使得原图成为一条链，如果能，你还需要求出这条链的最大长度。

输入格式

从文件$merge.in$中读入数据。
第一行两个正整数$n,m$，表示图的点数和边数。
接下来m行，每行两个正整数$u,v$，表示$u$和$v$之间有一条无向边。

输出格式

输出到文件$merge.out$中。
如果能通过若干次合并操作使得原图成为一条链，输出链的最大长度，否则输出$-1$。

样例

样例输入1：

5 4
1 2
2 3
3 4
3 5

样例输出1：

样例输入2：

4 6
1 2
2 3
1 3
3 4
2 4
1 4

样例输出2：

-1

数据范围与提示

对于$30\%$的数据，$n<10$
对于$70\%$的数据，$n<2,000$
对于$100\%$的数据，$n\leqslant 1,000,m\leqslant 10^5$

题解

画画图便会发现，如果出现奇环则一定无解；最长链即为图的直径，答案就是每一个联通块直径和。

二分图染色即可，再求图的直径就好了。

时间复杂度：$\Theta(n^2)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

struct rec{int nxt,to;}e[200001];

int head[1001],cnt,tot;

int col[1001],bel[1001],len[1001];

int dis[1001];

bool vis[1001];

int ans;

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void dfs(int x,int c,int p)

{

	col[x]=c;bel[x]=p;

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(!col[e[i].to])dfs(e[i].to,-c,p);

		if(col[x]==col[e[i].to]){puts("-1");exit(0);}

	}

}

int Dij(int x)

{

	int res=0;

	memset(dis,0x3f,sizeof(dis));

	memset(vis,0,sizeof(vis));

	dis[x]=0;

	q.push(make_pair(0,x));

	while(!q.empty())

	{

		int flag=q.top().second;

		q.pop();

		if(vis[flag])continue;

		vis[flag]=1;

		res=max(res,dis[flag]);

		for(int i=head[flag];i;i=e[i].nxt)

			if(dis[e[i].to]>dis[flag]+1)

			{

				dis[e[i].to]=dis[flag]+1;

				q.push(make_pair(dis[e[i].to],e[i].to));

			}

	}

	return res;

}

int main()

{

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

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

	{

		int x,y;

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

		add(x,y);add(y,x);

	}

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

		if(!col[i])dfs(i,1,++tot);

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

		len[bel[i]]=max(len[bel[i]],Dij(i));

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

		ans+=len[i];

	printf("%d",ans);

	return 0;

}

rp++

巴特西