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

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

    题解：思路还是比较简单的，直接遍历做生成树，相连两点不同色，这样保证满足条件，时间复杂度\(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;
}