题意
\(n(1 \le n \le 1000000)\)个城市，\(k(1 \le k \le n)\)个国家，\(m(1 \le m \le 1000000)\)条边。要求每个国家有且仅有一个首都，每条边两端的城市至少要有一个首都。判断是否有解。
分析
满足性问题。而且每个城市只有两种情况，首都or不是首都。所以考虑2-sat
题解
对于每一个点，拆点为\(i\)和\(i'\)，表示有首都和无首都。
对于每一个国家（假设有\(a\)个城市），由于只有一个首都，也就是说，假设这个国家的第\(j\)城市是首都，则前\(j-1\)个城市和后\(a-j\)个城市都不是首都！对应着前缀和和后缀和为0！ 所以我们对每个国家建立前缀和和后缀和的结点，由于只有两种情况，0和1，所以照样用2-sat可以解决。 至于怎么连边，自己yy一下，很简单的。#includeusing namespace std;const int N=1000005*6, M=1000005*12;int ihead[N], cnt, FF[N], LL[N], p[N], scc, tot;struct E { int next, to;}e[M];void add(int x, int y) { e[++cnt]=(E){ihead[x], y}; ihead[x]=cnt;}void dfs(int x) { static int tid=0, s[N], vis[N], top=0; s[++top]=x; vis[x]=1; FF[x]=LL[x]=++tid; for(int i=ihead[x]; i; i=e[i].next) { int y=e[i].to; if(!FF[y]) { dfs(y); LL[x]=min(LL[x], LL[y]); } else if(vis[y]) { LL[x]=min(LL[x], FF[y]); } } if(FF[x]==LL[x]) { ++scc; int y; do { y=s[top--]; vis[y]=0; p[y]=scc; } while(x!=y); }}bool check() { for(int i=1, all=tot<<1|1; i<=all; ++i) { if(!FF[i]) { dfs(i); } } for(int i=1; i<=tot; ++i) { if(p[i<<1]==p[i<<1|1]) { return 0; } } return 1;}int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=m; ++i) { int x, y; scanf("%d%d", &x, &y); add(x<<1|1, y<<1); add(y<<1|1, x<<1); } tot=n; for(int j=1; j<=k; ++j) { scanf("%d", &m); for(int i=1; i<=m; ++i) { int a; scanf("%d", &a); int now=tot+i; if(i!=1) { add(now<<1|1, (now-1)<<1|1); add((now-1)<<1, now<<1); add(a<<1, (now-1)<<1|1); } else { add(a<<1|1, now<<1|1); } add(now<<1|1, a<<1|1); add(a<<1, now<<1); now=tot+m+i; if(i!=m) { add(now<<1|1, (now+1)<<1|1); add((now+1)<<1, now<<1); add(a<<1, (now+1)<<1|1); } else { add(a<<1|1, now<<1|1); } add(now<<1|1, a<<1|1); add(a<<1, now<<1); } tot+=2*m; } puts(check()?"TAK":"NIE"); return 0;}