[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]D Dendroctonus
[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]F False Intelligence

[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]E Election Frenzy

Zarxdy34 posted @ 2017年10月17日 18:53 in Codeforces with tags DFS 并查集 , 963 阅读

    题目大意:给出一个无向图,要求给图黑白染色,要求每个点和它相邻的点中至少有一个白点和一个黑点,输出任意一种方案。由于边数可能非常大,所以某些点给出的信息是所有不与它相连的点。

    题解:思路还是比较简单的,直接遍历做生成树,相连两点不同色,这样保证满足条件,时间复杂度\(O(n+m)\),至于遍历时怎么处理边非常多的问题,可以随便写个数据结构(set之类的)搞搞,这里我用的是并查集。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,maxm=5e5+10;

char readchar() {char ch;while ((ch=getchar())!='C' && ch!='N');return ch;}

int head[maxn],nxt[maxm],E[maxm],P[maxn],Ecnt;
int Col[maxn];
int vis[maxn];
int fa[maxn];
int n;

void Add_Edge(int x,int y)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;
}

int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}

void DFS(int x,int col)
{
	vis[x]=1;
	fa[x]=Find(x-1);
	Col[x]=col;
	if (P[x]==0)
	{
		for (int i=head[x];i;i=nxt[i])
			if (!vis[E[i]]) DFS(E[i],col^1);
	}
	else
	{
		int t=n+1;
		for (int i=head[x];i;i=nxt[i])
		{
			t=Find(t-1);
			while (t>E[i]) DFS(t,col^1),t=Find(t-1);
			t=E[i];
		}
		t=Find(t-1);
		while (t>0) DFS(t,col^1),t=Find(t-1);
	}
}

int temp[maxn];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int k;
		char ch=readchar();
		if (ch=='N') P[i]=1;
		scanf("%d",&k);
		if ((k==0 && P[i]==0) || (k==n-1 && P[i]==1))
		{
			printf("Impossible\n");
			return 0;
		}
		for (int j=0;j<k;j++) scanf("%d",&temp[j]);
		sort(temp,temp+k);
		for (int j=0;j<k;j++) Add_Edge(i,temp[j]);
	}
	for (int i=0;i<=n;i++) fa[i]=i;
	for (int i=1;i<=n;i++) if (!vis[i]) DFS(i,0);
	for (int i=1;i<=n;i++) printf("%c",Col[i]==0?'V':'S');
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter