程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> csu 1356 Catch （判斷奇環）

csu 1356 Catch （判斷奇環）

編輯：C++入門知識

csu 1356 Catch

題意：給定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;
vectoradj[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;
vectoradj[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
*/