hdu 5222-白红宇

hdu 5222

阅读量：5279 次

发布时间：2019-06-14

本文共 2496 字，大约阅读时间需要 8 分钟。

首先对于所有的无向边，我们使用并查集将两边的点并起来若一条边未合并之前，两端的点已经处于同一个集合了，那么说明必定存在可行的环（因为这两个点处于同一个并查集集合中，那么它们之间至少存在一条路径）如果上一步没有判断出环，那么仅靠无向边是找不到环的考虑到，处于同一个并查集集合中的点之间必定存在一条路径互达，因此将一个集合的点合并之后，原问题等价于在新生成的有向图中是否有环我们知道，有向无环图必定存在拓扑序，因此只需使用拓扑排序判定即可时间复杂度

1 /*Author :usedrose  */  2 /*Created Time :2015/7/31 18:35:37*/  3 /*File Name :2.cpp*/  4 #pragma comment(linker, "/STACK:102400000,102400000")   5 #include 
     
        6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10 #include 
          
            11 #include 
           
             12 #include 
            
              13 #include 
             
               14 #include 
              
                15 #include 
               
                 16 #include 
                
                  17 #include 
                 
                   18 #include 
                  
                    19 #include 
                   
                     20 #include 
                     21 #define INF 0x3f3f3f3f 22 #define eps 1e-8 23 #define pi acos(-1.0) 24 #define MAXN 1000000 25 #define OK cout << "ok" << endl; 26 #define o(a) cout << #a << " = " << a << endl 27 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl 28 using namespace std; 29 typedef long long LL; 30 31 int fa[MAXN]; 32 int n, m1, m2; 33 vector
                     
                       G[MAXN]; 34 int vis[MAXN], ind[MAXN]; 35 36 int findset(int x) 37 { 38 return fa[x] = fa[x] == x ? x:findset(fa[x]); 39 } 40 41 bool merg(int a, int b) 42 { 43 int x = findset(a); 44 int y = findset(b); 45 if (x == y) return false; 46 fa[x] = y; 47 return true; 48 } 49 50 void init() 51 { 52 for (int i = 1;i <= n; ++ i) { 53 fa[i] = i; 54 ind[i] = 0; 55 G[i].clear(); 56 } 57 } 58 59 60 bool toposort() 61 { 62 queue
                      
                        Q; 63 for (int i = 1;i <= n; ++ i) { 64 if (ind[i] == 0 && fa[i] == i) 65 Q.push(i); 66 } 67 while (!Q.empty()) { 68 int t = Q.front(); 69 Q.pop(); 70 for (int i = 0;i < G[t].size(); ++ i) { 71 int v = G[t][i]; 72 if (--ind[v] == 0) 73 Q.push(v); 74 } 75 } 76 for (int i = 1;i <= n; ++ i) 77 if (ind[i]) 78 return false; 79 return true; 80 } 81 82 int main() 83 { 84 //freopen("data.in","r",stdin); 85 //freopen("data.out","w",stdout); 86 int T; 87 scanf("%d", &T); 88 while (T--) { 89 scanf("%d%d%d", &n, &m1, &m2); 90 init(); 91 bool ans = true; 92 int x, y; 93 for (int i = 1;i <= m1; ++ i) { 94 scanf("%d%d", &x, &y); 95 ans &= merg(x, y); 96 } 97 98 for (int i = 1;i <= m2; ++ i) { 99 scanf("%d%d", &x, &y);100 x = findset(x);101 y = findset(y); 102 G[x].push_back(y);103 ind[y]++;104 }105 if (ans == 0) {106 puts("YES");107 continue;108 }109 110 ans = toposort();111 puts(ans? "NO" : "YES");112 }113 return 0;114 }

转载于:https://www.cnblogs.com/usedrosee/p/4692992.html

你可能感兴趣的文章