Graph and String

wjh15101051's space

卧薪尝胆，厚积薄发。

Graph and String

Date: Sat Dec 22 10:59:08 CST 2018

In Category: NoCategory

Description：

一个字符串 $\Sigma=\{a,b,c\}$ ，如果 $s[i]$ 和 $s[j]$ 相邻或相同，就连一条无向边 $(i,j)$ ，给出最后的图，构造字符串。

$1\leqslant n\leqslant 500$

Solution：

先取补图，那么在补图中度数为 $0$ 的点一定是 $b$ ，否则一条边连的两个一定是 $a$ 和 $c$ ，于是二分图染色即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 510

bool ex[MAXN][MAXN];

bool col[MAXN];

bool vis[MAXN];

int deg[MAXN];

bool mark(int k)

{

	vis[k] = true;

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

	{

		if(i == k)continue;

		if(ex[i][k] || ex[k][i])continue;

		++deg[k];

		if(vis[i])

		{

			if(col[i] == col[k])return false;

		}

		else

		{

			col[i] = col[k] ^ 1;

			if(!mark(i))return false;

		}

	}

	return true;

}

int main()

{

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

	int a,b;

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

	{

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

		ex[a][b] = true;

	}

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

	{

		if(!vis[i])

		{

			if(!mark(i))

			{

				puts("No");

				return 0;

			}

		}

	}

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

	{

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

		{

			if(i == j)continue;

			if(ex[i][j] || ex[j][i])

			{

				if(deg[i] != 0 && deg[j] != 0 && (col[i] ^ col[j]))

				{

					puts("No");

					return 0;

				}

			}

		}

	}

	puts("Yes");

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

	{

		if(deg[i] == 0)putchar('b');

		else if(col[i])putchar('a');

		else putchar('c');

	}

	return 0;

}

In tag: 图论-二分图染色

wjh15101051