图论--2-SAT--HDOJ/HDU 1824 Let's go home
图论--2-SAT--HDOJ/HDU 1824 Let's go home
Problem Description 小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。 —— 余光中
集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。
Input 第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。 接下来有T行，每行三个整数，表示一个队的队员编号，第一个队员就是该队队长。 然后有M行，每行两个整数，表示一对队员的编号。 每个队员只属于一个队。队员编号从0开始。
Output 可行输出yes，否则输出no，以EOF为结束。
Sample Input 1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4
Sample Output yes no
（1）题目第一个条件：每一个队或者队长留下或者其与两名队员同时留下，或者表明只能为两种情况中的一种；假设三人为A,B,C，队长为A，0表示不留下，1表示留下，因为B与C同时留下或者不留下，只要B，C中其中一个没有留下或者留下，则B,C中另一个也同样留下或者不留下，所以可以从该条件中推导出六条等价关系，即A不留下->B，C同时留下，A留下->B，C同时不留下，B留下->C留下，A不留下，B留下->C留下，A不留下，C留下->B留下，A不留西，C不留下->B不留下，A留下；
（2）题目中第二个条件：每一对队员，如果队员A留下，则B必须回家休息，或者B留下，A必须回家休息；则可以推导出两条等价式：A留下->B不留下，B留下->A不留下，注意在这个条件中可以A，B都不留下；
AC代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#define MAXN 7000+10
#define MAXM 400000
#define INF 1000000
using namespace std;
vector<int> G[MAXN];
int low[MAXN], dfn[MAXN];
int dfs_clock;
int sccno[MAXN], scc_cnt;
stack<int> S;
bool Instack[MAXN];
int N, M;
void init()
{
for(int i = 0; i <=6*N; i++) G[i].clear();
while(S.size()) S.pop();
dfs_clock=scc_cnt=0;
}
void getMap()
{
int a,b,c;
for(int i=0;i<N;i++)
{
scanf("%d %d %d",&a,&b,&c);
G[a+N*3].push_back(b);
G[a+N*3].push_back(c);
G[b+3*N].push_back(a);
G[c+3*N].push_back(a);
}
while(M--)
{
scanf("%d%d",&a,&b);
G[a].push_back(b+N*3);
G[b].push_back(a+N*3);
}
}
void tarjan(int u, int fa)
{
int v;
low[u] = dfn[u] = ++dfs_clock;
S.push(u);
Instack[u] = true;
for(int i = 0; i < G[u].size(); i++)
{
v = G[u][i];
if(!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(Instack[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
scc_cnt++;
for(;;)
{
v = S.top(); S.pop();
Instack[v] = false;
sccno[v] = scc_cnt;
if(v == u) break;
}
}
}
void find_cut(int l, int r)
{
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(sccno, 0, sizeof(sccno));
memset(Instack, false, sizeof(Instack));
dfs_clock = scc_cnt = 0;
for(int i = l; i <= r; i++)
if(!dfn[i]) tarjan(i, -1);
}
void solve()
{
for(int i = 0; i < 3*N; i++)
{
if(sccno[i] == sccno[i+3*N])//矛盾
{
printf("no\n");
return ;
}
}
printf("yes\n");
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
init();
getMap();
find_cut(0, 6*N-1);
solve();
}
return 0;
}