洛谷P1330封锁阳光大学—

题目：https://www.luogu.org/problemnew/show/P1330

此题我最初没有思路，暴搜而爆0；

然后才明白关键在于把所有点分成两类，因为可以发现点之间的关系是存在两两对立的；

这样一张图的情况就是固定的，确定一个点就能够确定其他所有点，因为一条边的两个点必然属于不同的类别，可以通过遍历边来进行深搜染色；

最后取各连通块中较少的那一类点，相加即为结果；

而若在染色中出现矛盾，则一定为“Impossible”。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int n,m,a,b,cnt[10005],ct,col[10005],s[5],ans;

struct N{

	int to;int next;

}edge[200005];//!

void add(int x,int y)

{

	ct++;

	edge[ct].to=y;

	edge[ct].next=cnt[x];

	cnt[x]=ct;

}

void dfs(int x)

{

	for(int i=cnt[x];i;i=edge[i].next)

	{

		int v=edge[i].to;

		if(col[v]==col[x])

		{

			printf("Impossible");

			exit(0);

		}

		if(!col[v])

		{

			col[v]=3-col[x];

			s[col[v]]++;

			dfs(v);

		}

	}

}

int main()

{

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

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);add(b,a);

	}

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

	{

		int v=edge[i].to;

		s[1]=0;s[2]=0;

		if(!col[v])

		{

			col[v]=1;

			s[col[v]]++;

			dfs(v);

			ans+=min(s[1],s[2]);

		}

	}

	printf("%d",ans);

	return 0;

}

巴特西

洛谷P1330封锁阳光大学——图的染色

最新文章

热门文章