Let's go home

Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2103 Accepted Submission(s): 903

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

Author

威士忌

Source

HDOJ 2007 Summer Exercise（3）- Hold by Wiskey

2-SAT 建图

 //2017-08-27

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int N = ;

 const int M = N*N;

 int head[N], rhead[N], tot, rtot;

 struct Edge{

     int to, next;

 }edge[M], redge[M];

 void init(){

     tot = ;

     rtot = ;

     memset(head, -, sizeof(head));

     memset(rhead, -, sizeof(rhead));

 }

 void add_edge(int u, int v){

     edge[tot].to = v;

     edge[tot].next = head[u];

     head[u] = tot++;

     redge[rtot].to = u;

     redge[rtot].next = rhead[v];

     rhead[v] = rtot++;

 }

 vector<int> vs;//后序遍历顺序的顶点列表

 bool vis[N];

 int cmp[N];//所属强连通分量的拓扑序

 //input: u 顶点

 //output: vs 后序遍历顺序的顶点列表

 void dfs(int u){

     vis[u] = true;

     for(int i = head[u]; i != -; i = edge[i].next){

         int v = edge[i].to;

         if(!vis[v])

           dfs(v);

     }

     vs.push_back(u);

 }

 //input: u 顶点编号; k 拓扑序号

 //output: cmp[] 强连通分量拓扑序

 void rdfs(int u, int k){

     vis[u] = true;

     cmp[u] = k;

     for(int i = rhead[u]; i != -; i = redge[i].next){

         int v = redge[i].to;

         if(!vis[v])

           rdfs(v, k);

     }

 }

 //Strongly Connected Component 强连通分量

 //input: n 顶点个数

 //output: k 强连通分量数;

 int scc(int n){

     memset(vis, , sizeof(vis));

     vs.clear();

     for(int u = ; u < n; u++)

       if(!vis[u])

         dfs(u);

     int k = ;

     memset(vis, , sizeof(vis));

     for(int i = vs.size()-; i >= ; i--)

       if(!vis[vs[i]])

         rdfs(vs[i], k++);

     return k;

 }

 void solve(int n){

     for(int i = ; i < n; i++){

         if(cmp[i] == cmp[i+n]){//a和NOT a在同一个强连通分量中，布尔方程无解

             cout<<"no"<<endl;

             return;

         }

     }

     cout<<"yes"<<endl;//布尔方程有解

     return;

 }

 int main()

 {

     std::ios::sync_with_stdio(false);

     //freopen("inputB.txt", "r", stdin);

     int t, m;

     while(cin>>t>>m){

         init();

         int MAXID = *t;

         int a, b, c;

         for(int i = ; i < t; i++){

             cin>>a>>b>>c;

             add_edge(a+MAXID, b);// NOT a -> b

             add_edge(a+MAXID, c);// NOT a -> c

             add_edge(b+MAXID, a);// NOT b -> a

             add_edge(c+MAXID, a);// NOT c -> a

             //add_edge(b, c);

             //add_edge(c, b);

         }

         for(int i = ; i < m; i++){

             cin>>a>>b;

             add_edge(a, b+MAXID);

             add_edge(b, a+MAXID);

         }

         scc(MAXID<<);

         solve(MAXID);

     }

     return ;

 }

lcy

HDU1824(2-SAT)