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

 

2-SAT 建图

1 //2017-08-27  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7   8 using namespace std;  9  10 const int N = 5010; 11 const int M = N*N; 12 int head[N], rhead[N], tot, rtot; 13 struct Edge{ 14     int to, next; 15 }edge[M], redge[M]; 16  17 void init(){ 18     tot = 0; 19     rtot = 0; 20     memset(head, -1, sizeof(head)); 21     memset(rhead, -1, sizeof(rhead)); 22 } 23  24 void add_edge(int u, int v){ 25     edge[tot].to = v; 26     edge[tot].next = head[u]; 27     head[u] = tot++; 28  29     redge[rtot].to = u; 30     redge[rtot].next = rhead[v]; 31     rhead[v] = rtot++; 32 } 33  34 vector
           
             vs;//后序遍历顺序的顶点列表 35 bool vis[N]; 36 int cmp[N];//所属强连通分量的拓扑序 37 38 //input: u 顶点 39 //output: vs 后序遍历顺序的顶点列表 40 void dfs(int u){ 41 vis[u] = true; 42 for(int i = head[u]; i != -1; i = edge[i].next){ 43 int v = edge[i].to; 44 if(!vis[v]) 45 dfs(v); 46 } 47 vs.push_back(u); 48 } 49 50 //input: u 顶点编号; k 拓扑序号 51 //output: cmp[] 强连通分量拓扑序 52 void rdfs(int u, int k){ 53 vis[u] = true; 54 cmp[u] = k; 55 for(int i = rhead[u]; i != -1; i = redge[i].next){ 56 int v = redge[i].to; 57 if(!vis[v]) 58 rdfs(v, k); 59 } 60 } 61 62 //Strongly Connected Component 强连通分量 63 //input: n 顶点个数 64 //output: k 强连通分量数; 65 int scc(int n){ 66 memset(vis, 0, sizeof(vis)); 67 vs.clear(); 68 for(int u = 0; u < n; u++) 69 if(!vis[u]) 70 dfs(u); 71 int k = 0; 72 memset(vis, 0, sizeof(vis)); 73 for(int i = vs.size()-1; i >= 0; i--) 74 if(!vis[vs[i]]) 75 rdfs(vs[i], k++); 76 return k; 77 } 78 79 void solve(int n){ 80 for(int i = 0; i < n; i++){ 81 if(cmp[i] == cmp[i+n]){ //a和NOT a在同一个强连通分量中，布尔方程无解 82 cout<<"no"<
            
             >t>>m){ 96 init(); 97 int MAXID = 3*t; 98 int a, b, c; 99 for(int i = 0; i < t; i++){100 cin>>a>>b>>c;101 add_edge(a+MAXID, b);// NOT a -> b102 add_edge(a+MAXID, c);// NOT a -> c103 add_edge(b+MAXID, a);// NOT b -> a104 add_edge(c+MAXID, a);// NOT c -> a105 //add_edge(b, c);106 //add_edge(c, b);107 }108 for(int i = 0; i < m; i++){109 cin>>a>>b;110 add_edge(a, b+MAXID);111 add_edge(b, a+MAXID);112 }113 scc(MAXID<<1);114 solve(MAXID);115 }116 return 0;117 }