题目链接

题意：判断所给的图中 两点间的路径是否唯一（不走回头路）

坑点/思想：

  1. 没加入一条边， 判断他们的祖先是否相同，如果相同， 那么他们之间的路径不唯一
  2. 判断这个图是否只有一个连通块（用set储存（突然又想到直接用队列更好一些 ）然后判断tofind（i） == i 的个数 如果大于1， 则证明不仅仅只有一个连通块）
  3. 针对上面的题， 特殊情况， 边界情况要考虑在内

Ac代码：（set实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#include <bits/stdc++.h>
#include <iostream>
#include "algorithm"
#include "cstdio"
#include "set"
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
int f[N];

set<int>se;
set<int>::iterator it;
int tofind(int x){
    if (f[x] != x){
        f[x] = tofind(f[x]);
    }
    return f[x];
}
void tojoin(int a, int b){
    a = tofind(a);
    b = tofind(b);
    if (a != b){
        f[a] = b;
    }
}
void init(){
    for (int i = 0; i <= N; i++){
        f[i] = i;
    }
    se.clear();
}
int main(){
    int a, b;
    int f = 0;
    init();
    while(cin >> a >> b){
        if (!a && !b){
            if (f)
                puts("No");
            else{
                int sum = 0;
                for (it = se.begin(); it != se.end(); it ++){
                    if (tofind(*it) == *it)
                        sum++;
                    if (sum >= 2)
                        break;
                }
                if (sum >= 2)
                    puts("No");
                else{
                    puts("Yes");
                }
            }
            f = 0;
            init();
        }
        else if (a == -1 && b == -1)
            break;
        else{
            se.insert(a);
            se.insert(b);
            if (tofind(a) != tofind(b))
                tojoin(a, b);
            else
                f = 1;
        }
    }
    return 0;
}

Ac代码：（队列实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include <bits/stdc++.h>
#include <iostream>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
int f[N];

queue<int>q;
int tofind(int x){
    if (f[x] != x){
        f[x] = tofind(f[x]);
    }
    return f[x];
}
void tojoin(int a, int b){
    a = tofind(a);
    b = tofind(b);
    if (a != b){
        f[a] = b;
    }
}
void init(){
    for (int i = 0; i <= N; i++){
        f[i] = i;
    }
    while(!q.empty())
        q.pop();
}
int main(){
    int a, b;
    int f = 0;
    init();
    while(cin >> a >> b){
        if (!a && !b){
            if (f)
                puts("No");
            else{
                int sum = 0;
                while(!q.empty()){
                    int k = q.front();
                    q.pop();
                    if (tofind(k) == k)
                        sum++;
                    if (sum >= 2)
                        break;
                }
                if (sum >= 2)
                    puts("No");
                else{
                    puts("Yes");
                }
            }
            f = 0;
            init();
        }
        else if (a == -1 && b == -1)
            break;
        else{
            q.push(a);
            q.push(b);
            if (tofind(a) != tofind(b))
                tojoin(a, b);
            else
                f = 1;
        }
    }
    return 0;
}