Cod sursa(job #2168003)

Utilizator tuddor1234Turdasan Tudor tuddor1234 Data 14 martie 2018 09:06:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

int TT[100002],RG[100002];
int n,m,x,y;

int find(int x)
{
    if(TT[x]==x) return x;
    else TT[x]=find(TT[x]);
    return TT[x];
}

void unite(int x,int y)
{
    int minim=min(x,y);
    int maxim=max(x,y);
    TT[maxim]=minim;
    RG[maxim]+=RG[minim];
}



int main()
{
    fin>>n>>m;
   int cate=n;
    for(int i=1;i<=n;i++) {RG[i]=1;TT[i]=i;}

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(find(x)!=find(y))
        {
            unite(find(x),find(y));
            cate--;
        }
    }
   fout<<cate;


    return 0;
}