Cod sursa(job #2094826)

Utilizator alexandra_paticaAndreea Alexandra Patica alexandra_patica Data 26 decembrie 2017 16:50:28
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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++) c[i].push_back(i);
    for (i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        rx=root(x);
        ry=root(y);
        if ( rx!=ry){
            if (p[rx]>=p[ry]){
//                for (j=0; j<c[y].size(); j++)
//                    c[rx].push_back(c[y][j]);
//                c[y].clear();
                uni(rx, ry);
                nr--;
            }
        }
        else{
//            for (j=0; j<c[x].size(); j++)
//                c[ry].push_back(c[x][j]);
//            c[x].clear();
            uni(rx, ry);
            nr--;
        }
    }
    printf("%d", nr);
    return 0;
}