1.并查集

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
#include <iostream>

using namespace std;
const int N=1e3+10;
int Father[N];
void Make_Set(int x)
{
    Father[x]=0;
}
int Find(int x)
{
    if(Father[x]<=0) return x;
    Father[x]=Find(Father[x]);
    return Father[x];
}
void Union(int x,int y)
{
    int fx=Find(x),fy=Find(y);
    if(fx==fy) return;
    if(Father[x]<Father[y])
        Father[fy]=fx;
    else{
        Father[fx]=fy;
        if(Father[fx]==Father[fy])
            Father[fy]--;
    }
}
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        Make_Set(i);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        Union(a,b);
    }
    int cnt=0;
    for(int i=0;i<q;i++)
    {
        int c,d;cin>>c>>d;
        if(Find(c)==Find(d))
            cout<<"In the same gang."<<endl;
        else cout<<"In different gangs."<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        if(Father[i]<=0)
            cnt++;
    }
    cout<<cnt<<endl;
}

2.树的最近公共祖先

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

const int N=1e3+10;
int ancester[N];
int depth[N];
void DFS(node* t,node* anc)
{
    if(t==NULL) return;
    if(anc==NULL)
    {
        ancester[t->data]=0;
        depth[t->data]=1;
    }
    else
    {
        ancester[t->data]=anc->data;
        depth[t->data]=depth[anc->data]+1;
    }
    for(node* tmp=t->firstChild;tmp!=NULL;tmp=tmp->nextBrother)
    {
        DFS(tmp,t);
    }
}
int LeastCommonAncestors(node *root, int a, int b)
{
    DFS(root,NULL);
    while(depth[a]<depth[b])
        b=ancester[b];
    while(depth[b]<depth[a])
        a=ancester[a];
    while(a!=b)
    {
        a=ancester[a];
        b=ancester[b];
    }
    return a;
}