Cod sursa(job #1934128)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 21 martie 2017 10:26:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int tata[100002],h[100002];
int myfind(int x)
{
    if(tata[x]==0)
        return x;
    return myfind(tata[x]);
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,i,x,y,m,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a=myfind(x);
        b=myfind(y);
        if(a!=b)
        {
            if(h[a]>h[b])
                tata[b]=a;
            else if(h[b]>h[a])
                tata[a]=b;
            else
            {
                tata[a]=b;
                h[b]++;
            }
        }
    }
    int cnt=0;
    for(i=1;i<=n;i++)
        if(tata[i]==0)
            cnt++;
        printf("%d",cnt);
    return 0;
}