Cod sursa(job #2069658)

Utilizator novistaAlex Staicu novista Data 18 noiembrie 2017 17:48:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#define DIM 100020
#define DIM2 200020
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
vector <vector <int> > comp(DIM2);
int n,m,nr;
int t[DIM],r[DIM];
int Find( int x)
{
    int rad,elem;
    rad=x;
    while (t[rad]!=0)
        rad=t[rad];
    while (t[x]!=0)
    {
        elem=t[x];
        t[x]=rad;
        x=elem;
    }
    return rad;
}
void Union (int x,int y)
{
    if (r[x]>r[y])
        t[y]=x;
    else if (r[x]<r[y])
            t[x]=y;
         else
         {
             t[x]=y;
             r[y]++;
         }
}
int main()
{
    int x,y,rad1,rad2,i,j;
    fin>>n>>m;
    nr=n;
    for (i=1;i<=n;i++)
        comp[i].push_back(i);
    while (m>0)
    {
        fin>>x>>y;
        rad1=Find(x);
        rad2=Find(y);
        if (rad1!=rad2)
        {
            if (r[rad1]>=r[rad2])
            {
                for (i=0;i<comp[y].size();i++)
                    comp[x].push_back(comp[y][i]);
                comp[y].clear();
                Union(rad1,rad2);
                nr--;
            }
            else
            {
                for (i=0;i<comp[x].size();i++)
                    comp[y].push_back(comp[x][i]);
                comp[x].clear();
                Union(rad1,rad2);
                nr--;
            }
        }
        m--;
    }
    fout<<nr<<"\n";
    /*for (i=1;i<=n;i++)
        if (comp[i].empty()==0)
        {
            for (j=0;j<comp[i].size();j++)
                fout<<comp[i][j]<<" ";
            fout<<"\n";
        }
        */
    fin.close();
    fout.close();
    return 0;
}