Cod sursa(job #1713921)

Utilizator oana28Oana Mitoiu oana28 Data 6 iunie 2016 22:11:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#include<bitset>
using namespace std;
#define NMAX 100005
ifstream fin("dfs.in");
ofstream fout("dfs.out");
bitset <NMAX> ok;
int n,m,k,x,y,GR[NMAX];
int grupa(int k)
{
    if (GR[k]==k) return k;
    GR[k]=grupa(GR[k]);
    return GR[k];
}
void unifica(int k1, int k2)
{
    int r1=grupa(k1), r2=grupa(k2);
    GR[r2]=r1;
}
int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=n;++i)
        GR[i]=i;
    for (i=0;i<m;++i)
    {
        fin>>x>>y;
        unifica(x,y);
    }
    for (i=1;i<=n;++i)
        ok[grupa(i)]=1;
    for (i=1;i<=n;++i)
        if (ok[i])
            ++k;
    fout<<k<<"\n";
    return 0;
}