P5836 [USACO19DEC]Milk Visits S 从并查集到LCA（最近公共祖先） Tarjan算法 （初级）

int find(int num)
{
    if(die[num]==num)
    {
        return num;
    }
        die[num]= find(die[num]);//记忆化，缩减递归产生的重复，找过的就记下来。
    return die[num];
}

#include
#includeusing namespace std;
int n,m,p,c,d,die[5050];
int find(int num)
{
    if(die[num]==num)//发现他自己主宰自己，直接返回他自己（递归的出口）
    {
        return num;
    }
    die[num]= find(die[num]);//如果不是，递归找他爸爸的爸爸
    return die[num];
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i)
    {
        die[i]=i;
    }
    for(int i=1;i)
    {
        scanf("%d%d",&c,&d);
        die[find(c)]=find(d);//找到c的爸爸的爸爸，然后让c的爸爸认d的爸爸为爸爸……  当然可以c和d反过来存。
    }

    for(int i=1;i)
    {
        scanf("%d%d",&c,&d);
        if(find(c)==find(d))//查询一下他们的爸爸是不是同一人
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }        
} 

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 nn 和道路数目 mm ；随后的 mm 行对应 mm 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 11 到 nn 编号。

注意：两个城市间可以有多条道路相通。

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

#include
#include
#includeusing namespace std;
int n,m,die[1000],c,d,e,f,ans;
int find(int num)
{
    if (die[num]==num)return num;
    return  die[num]=find(die[num]);//还是记忆化，注意养成递归思考避免重复运算的习惯
}
int main()
{
    while(1)
    {
        scanf("%d",&c);
        if(c==0)break;
        for(int i=1;ii;
        ans=0;
        scanf("%d",&d);
        for(int i=0;i)
        {
            scanf("%d%d",&e,&f);
            die[find(e)]=find(f);
        }
        for(int i=1;i)
        {
            if(die[i]==i)ans++;//统计多少自己管理自己的孤儿，每个孤儿需要一条道路
        }
        if(ans==0){
            printf("%d\n",0);
        }
        else printf("%d\n",ans-1);    
    }
    
}

#include
#includeusing namespace std;
int n,m,a,b,die[100010],ans;
char c,se[100010];    
int find(int num)
{
    if(die[num]==num)
    {
        return num;
    }
    die[num]=find(die[num]);
    return die[num];    
}
int main()
{
    cin>>n>>m;
    for(int i=1;i)
    {
        die[i]=i;
        cin>>se[i];
    }
    for(int i=1;i)
    {
        scanf("%d %d",&a,&b);

        if(se[a]==se[b])
        {
            die[find(a)]=find(b);//颜色相同还联通，集合起来。
        }
    }
    for(int i=1;i)
    {    
        scanf("%d%d",&a,&b);
        scanf(" %c",&c);//这里特别注意%c之前的空格，可以抵消掉输入时候的空格，否则c就存个空格\0
        if(se[a]!=c)//如果起步就不是他喜欢的牛奶
        {
            if(find(a)==find(b))//而且落脚和起步在一个联通块，别想了，一路上没有什么变化，都是不想喝的牛奶
            {
                printf("0");
            }
            else
            {
                printf("1");//起步和落脚不在一个联通块，说明有不同的牛奶，一定开心！
            }
        }
        else
        {
            printf("1");
        }
    }
}