Hdu 4751(2-SAT)

题目链接

思路：对于任意一个游客，要么属于第一个集合，要么属于第二个集合，因为题中的“关系”是单向的，

所以当两个人之间只有一条单向边时就意味着：如果A属于第一个集合，那么B就一定属于第二个集合，反之亦然。

这样就可以建图了。

Accepted Code:

 /*************************************************************************

     > File Name: 4751.cpp

     > Author: Stomach_ache

     > Mail: [email protected]

     > Created Time: 2014年08月09日 星期六 22时55分53秒

     > Propose: 2-SAT

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 bool a[maxn][maxn];

 struct SCC {

       int n;

     vector<int> g[maxn<<];

     vector<int> rg[maxn<<];

     vector<int> vs;

     bool vis[maxn<<];

     int cmp[maxn<<];

     void addEdge(int from, int to) {

         g[from].push_back(to);

         rg[to].push_back(from);

     }

     void init(int nn) {

         this->n = nn * ;

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

             g[i].clear();

             rg[i].clear();

         }

         vs.clear();

     }

     void dfs(int u) {

         vis[u] = true;

         for (int i = ; i < (int)g[u].size(); i++) {

               int v = g[u][i];

               if (!vis[v]) dfs(v);

         }

         vs.push_back(u);

     }

     void rdfs(int u, int k) {

         vis[u] = true;

         cmp[u] = k;

         for (int i = ; i < (int)rg[u].size(); i++) {

             int v = rg[u][i];

             if (!vis[v]) rdfs(v, k);

         }

     }

     int find_scc() {

         memset(vis, false, sizeof(vis));

         for (int i = ; i < n; i++) if (!vis[i]) dfs(i);

         memset(vis, false, sizeof(vis));

         int k = ;

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

              if (!vis[vs[i]]) rdfs(vs[i], k++);

         return k;

     }

 };

 SCC A;

 int main(void) {

       int n;

       while (~scanf("%d", &n)) {

           memset(a, false, sizeof(a));

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

             int to;

             while (scanf("%d", &to), to) {

                 a[i][to-] = true;

             }

         }

         A.init(n);

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

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

                   if (a[i][j]&&!a[j][i] || !a[i][j]&&a[j][i]) {

                     A.addEdge(i, j + n);

                     A.addEdge(i + n, j);

                 }

             }

         }

         A.find_scc();

         bool flag = true;

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

               if (A.cmp[i] == A.cmp[i+n]) {

                 flag = false;

                 break;

             }

         }

         puts(flag ? "YES" : "NO");

     }

     return ;

 }