Cod sursa(job #1462900)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 19 iulie 2015 13:34:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005

using namespace std;

vector<int> a[NMAX];
int rang[NMAX],uniune[NMAX],n,m,x,y,nrc,ac,b;

void create_union()
{
    for(int i=1;i<=n;i++)
    {
        uniune[i]=i;
        rang[i]=0;
    }
}

void unite_union(int r1,int r2)
{
    if(rang[r1]>rang[r2])
        uniune[r2]=r1;
    else
        uniune[r1]=r2;

    if(rang[r1]==rang[r2]) rang[r2]++;

}

int find_union(int x)
{
    int r,y;
   // cout << 1;
    for(r=x; uniune[r]!=r; r = uniune[r]);

    for(; x!=uniune[x]; )
    {
        y = uniune[x];
        uniune[x]=r;
        x=y;
    }
    //cout << 2;
    return r;
}
int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    in >> n >> m;
    create_union();
    for(int i=0;i<m;i++)
    {
        in >> x >> y;
       // a[x].push_back(y);
      //  a[y].push_back(x);
        if(find_union(x)!=find_union(y))
            unite_union(find_union(x),find_union(y));
    }
    /*
    for(int i=1;i<=n;i++)
    {
        ac = find_union(i);
        for(int j=0;j<a[i].size();j++)
            {
            b = find_union(a[i][j]);

            if(ac!=b)
                unite_union(ac,b);
            }
    }
    */
    for(int i=1;i<=n;i++)
        if(uniune[i]==i){
            nrc++;
            //cout << uniune[i] << endl;
        }

    out << nrc;
    return 0;
}