PA2010 Riddle
Time Limit: 30 Sec Memory Limit: 512 MB
Description
有n个城镇被分成了k个郡，有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。
Input
第一行有三个整数，城镇数n（1<=n<=106），边数m（0<=m<=106），郡数k（1<=k<=n）。
接下来m行，每行有两个整数ai和bi（ai≠bi），表示有一条无向边连接城镇ai和bi。
接下来k行，第j行以一个整数wj开头，后面是wj个整数，表示第j个郡包含的城镇。
Output
若有解输出TAK，否则输出NIE。
Sample Input
6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5
Sample Output
TAK
入门 2-SAT
这道题由于数据范围，不能直接建图。。。
然后就把一个地方分成两对点u u‘ U U’
u这一对代表这个点是不是他这个国家的首都。。。
U代表这个点及这个点之前的点中是否有首都。。。这个国家的城市的顺序就是他的输入顺序。。。
这好像是前缀优化。。。理所当然的就有了后缀优化了。。。（只是这次没有用）
然后判断是否可以就是找强连通分量，要是一对点都在一个强连通分量里面就凉了呀，不然一定可以。
网上看了一篇很好的博客说如果要找一组解的话。。
缩点建新图以后，根据对称性，每次找一个点（这个点的下一个点不能是他的对点），选这个点和这个点的下一个点，把他的对点和对点的前一个点给删了（好像是这样）
然后乱找好像不是很优雅，所以就反着按照拓扑序操作就好了。。。
建图还是写点小函数方便一些，别建昏了。。。。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e6 + 5;
int n, m, k, cnt, tnt, pre[maxn], low[maxn], dfn[maxn], scc[maxn];
vector<int> point[maxn];
stack<int> s;
inline void read(int&a)
{
char c;
while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';
while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
}
inline void connect(int a, int b)
{
if(a == -1 || b == -1) return;
point[a].push_back(b);
}
inline int u(int t){return (t << 1);}
inline int U(int t){return (t << 1) + (n << 1);}
inline int uu(int t){return (t << 1) ^ 1;}
inline int UU(int t){return ((t << 1) + (n << 1)) ^ 1;}
inline void putit()
{
read(n); read(m); read(k);
for(int a, b, i = 1; i <= m; ++i){
read(a); read(b); a--; b--;
connect(uu(a), u(b)); connect(uu(b), u(a));
}
for(int num, pr, x, w = 1; w <= k; ++w){
read(num); read(pr); pr--; pre[pr] = -1;
for(int i = 1; i < num; ++i){read(x); x--; pre[x] = pr; pr = x;}
}
}
inline void prepare()
{
for(int i = 0; i < n; ++i){
connect(u(i), U(i)); connect(UU(i), uu(i));
if(pre[i] >= 0){
connect(U(pre[i]), U(i)); connect(UU(i), UU(pre[i]));
connect(u(i), UU(pre[i])); connect(U(pre[i]), uu(i));
}
}
}
void tarjan(int t)
{
dfn[t] = low[t] = ++cnt; s.push(t);
for(int i = point[t].size() - 1; i >= 0; --i){
int now = point[t][i];
if(!dfn[now]){
tarjan(now); low[t] = min(low[t], low[now]);
}
else if(!scc[now]) low[t] = min(low[t], low[now]);
}
if(dfn[t] == low[t]){
tnt++;
while(1){
int now = s.top(); s.pop();
scc[now] = tnt;
if(now == t) break;
}
}
}
int main()
{
putit();
prepare();
for(int i = 0; i < 4 * n; ++i) if(!dfn[i]) tarjan(i);
for(int i = 0; i < 4 * n; ++i)
if(scc[i] == scc[i ^ 1]){
printf("NIE"); return 0;
}
printf("TAK");
return 0;
}