Cod sursa(job #1800392)

Utilizator roxanastRoxana Stiuca roxanast Data 7 noiembrie 2016 19:01:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#define NMAX 100000
using namespace std;
int n,m,t[NMAX+100],nivele[NMAX+100];
ifstream f("dfs.in");
ofstream g("dfs.out");
int gasesc(int c){
    if(c==t[c])
        return c;
    t[c]=gasesc(t[c]);
    return t[c];
}
void unesc(int a, int b){
    if(nivele[a]<nivele[b])
        t[a]=b;
    else
        if(nivele[a]>nivele[b])
        t[b]=a;
    else{
        t[a]=b;
        nivele[b]++;
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++){
        t[i]=i;
        nivele[i]=1;
    }
    for(int i=1;i<=m;i++){
        int x,y,a,b;
        f>>x>>y;
        if((a=gasesc(x))!=(b=gasesc(y)))
            unesc(a,b);
    }
    int nr=0;
    for(int i=1;i<=n;i++)
        if(t[i]==i)
        nr++;
    g<<nr;
    return 0;
}