csu 1356 Catch （判断奇环） - c++编程基础

题意：给定n个点，m条边的无向图（没有重边和子环）。从给定点出发，每个时间走到相邻的点，可以走重复的边，相邻时间不能停留在同一点，判断是否存在某个时间停留在任意的n个点。

分析：

（1）首先，和出发点的位置没有关系。因为可以走重复的边，且时间没有限制大小。

（2）图必须是联通的

（3）

1）图为2-0-1-3

从0点出发（时间为0），一个时间后到达1或2（时间为1），再一个时间后到达0或3（时间为2）。。。

可以发现，点分为两类，奇数时间到达和偶数时间到达，答案为NO

2）图为：2-0-1-2（奇环）

此图中的点，即可以在奇数时间到达，又可以在偶数时间到达。则答案为YES。比如都有个偶数的到达时间，在小时间在往返的走重复边后，（不改变奇偶，只改变大小，+2）

3）图为：2-0-1-3-2（偶环）

此图中的点和1)类似，同样分为两类。答案为NO

综上：所有点必须都能在奇数时间和偶数时间到达，则需要图能够改变到达点时间奇偶的结构。

由上可知，图中必须存在奇环。问题变成了，判断图是否存在奇环和是否连通

判断存在奇环的方法：

（1）二分图染色 dfs染色

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int maxn = 100010; const int MOD = 9997; int n; int m, st; int tot; vector
               
                adj[maxn]; int vis[maxn]; int fla; int dfs(int x, int fa, int val) { if (vis[x] == -1) vis[x] = val; else return vis[x]; tot++; for (int i = 0; i < adj[x].size(); i++) { int y = adj[x][i]; //if (y != fa) //{ if (vis[x] == dfs(y, x, vis[x] ^ 1)) fla = 1; //} } return vis[x]; } int main () { int T; cin >> T; int x, y; int ncase = 1; while (T--) { memset(vis, -1, sizeof(vis));///初始化为-1，染成0和1 cin >> n >> m >> st; for (int i = 0; i< n; i++) adj[i].clear(); while (m--) { scanf("%d%d", &x,&y); adj[x].push_back(y); adj[y].push_back(x); } fla = 0;///判断是否找到奇环 tot = 0;///记录联通的点数 dfs(st, -1, 0); printf("Case %d: ", ncase++); if (fla && tot == n) puts("YES"); else puts("NO"); } return 0; }

（2）二分图染色 bfs染色

（3）并查集

加权并查集的特例种类并查集。既可以判断连通性，也可以判断种类。

加权并查集，需要取模是，注意正确性，尤其是当有减法和除法。

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int maxn = 100010; const int MOD = 9997; int n; int m, st; int tot; vector
               
                adj[maxn]; int fa[maxn]; int val[maxn]; void init(int n) { for (int i = 0; i <= n; i++) { fa[i] = i; val[i] = 0; } } int find(int x) { if (x != fa[x]) { int oldfa = fa[x]; fa[x] = find(fa[x]); val[x] ^= val[oldfa]; // val[x] = (val[x] + val[oldfa]) % 2; } return fa[x]; } int main () { int T; cin >> T; int x, y; int ncase = 1; while (T--) { cin >> n >> m >> st; for (int i = 0; i < n; i++) adj[i].clear(); init(n); int fla = 0; if (n == 1) fla = 1; while (m--) { scanf("%d%d", &x,&y); adj[x].push_back(y); adj[y].push_back(x); int fax = find(x); int fay = find(y); if (fax != fay) { fa[fax] = fay; val[fax] = val[x] ^ val[y] ^ 1; // val[fax] = (val[x] - val[y] + 1 + 2) % 2; } else if (val[x] ^ val[y] == 0) fla = 1; } int fax = find(0); for (int i = 1; i < n; i++) if (find(i) != fax) { fla = 0; break; } printf("Case %d: ", ncase++); if (fla) puts("YES"); else puts("NO"); } return 0; } /* 2 3 3 0 0 1 0 2 1 2 2 1 0 0 1 */