您现在的位置: 主页 > 黑客联盟 > QQ密码破解 > 文章内容

小希的迷宫教你怎么盗QQ密码

作者: 盗QQ密码 来源:未知 时间: 2018-02-27 阅读:

小希的迷宫教你怎么盗QQ密码

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Problem Description 上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。
IDC94c6ytcTV+8r9ttTB0LHto6yx7cq+wcvSu8z1zai1wMGsvdO1xMG9uPa3v7zktcSx4LrFoaO3v7zktcSx4LrF1sHJ2c6qMaOsx9Kyu7Osuf0xMDAwMDCho8O/wb3X6cr9vt3Wrrzk09DSu7j2v9XQ0KGjIDxicj4K1fu49s7EvP7S1MG9uPYtMb3hzrKhozxicj4KCgogCjxicj4KCk91dHB1dAoKttTT2srkyOu1xMO/0rvX6cr9vt2jrMrks/a99rD8wKjSu9DQoaPI57n7uMPD1Lmst/u6z9Chz6O1xMu8wrejrMTHw7TK5LP2"Yes",否则输出"No"。

Sample Input
?
1
2
3
4
5
6
7
8
9
10
6 8  5 3  5 2  6 4
5 6  0 0
 
8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0
 
3 8  6 8  6 4
5 3  5 6  5 2  0 0
 
-1 -1

Sample Output
?
1
2
3
Yes
Yes
No
这道并查集的题目与其他题目相比,有几个要注意地方:1.房间编号并不是1—n,有些数字并没有出现,所以要用一个数组标记数字是否出现;2.如果查找到输入的两个数字的根节点相同,说明它们已经连通了,再加一条边就有多条相通的路径,用FLAG记录是否有多条相通路径;3.要判断所有房间是不是属于同一个集合。
?
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
//flag[i]数组标记i是否出现,FLAG标记是否有环,sum记录集合的个数
#include<STDIO.H>
const int N = 100005;
int flag[N], father[N];
void Init()
{
    for(int i = 0; i <= 100000; i++)
        flag[i] = 0, father[i] = i;
}
int Find(int x)
{
    if(x != father[x])
        father[x] = Find(father[x]);
    return father[x];
}
void Merge(int a, int b)
{
    int p = Find(a);
    int q = Find(b);
    if(p > q)
        father[p] = q;
    else
        father[q] = p;
}
int main()
{
    int a, b;
    while(~scanf("%d%d",&a,&b))
    {
 
        if(a == -1 && b == -1)
            break;
        Init();
        int FLAG = 0;
        while(1)
        {
            if(a == 0 && b == 0)
                break;
            if(Find(a) == Find(b))
                FLAG = 1;
            Merge(a,b);
            flag[a] = 1, flag[b] = 1;
            scanf("%d%d",&a,&b);
        }
        if(FLAG == 1)
            printf("No\n");
        else
        {
            int sum = 0;
            for(int i = 0; i <= 100000; i++)
                if(flag[i] && father[i] == i)
                    sum++;
            if(sum > 1)
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
    return 0;
}