Cod sursa(job #2094833)

Utilizator alexandra_paticaAndreea Alexandra Patica alexandra_patica Data 26 decembrie 2017 16:55:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <cstring>
using namespace std;

int n, m, i, t[100002], p[100002], cod, x, y, rx, ry, nr;

int root (int x)
{
    while (t[x]!=x) x=t[x];
    return x;
}
void uni (int x, int y)
{
    if (p[x]<p[y]) t[x]=y;
    if (p[x]>p[y]) t[y]=x;
    if (p[x]==p[y]){
        t[y]=x;
        p[x]++;
    }
}
int main ()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d%d", &n, &m);
    nr=n;
    for (i=1; i<=n; i++) t[i]=i;
    for (i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        rx=root(x);
        ry=root(y);
        if ( rx!=ry){
            uni(rx, ry);
            nr--;
        }
    }
    printf("%d", nr);
    return 0;
}