Cod sursa(job #1130188)

Utilizator rekingCretu Bogdan reking Data 28 februarie 2014 11:46:33
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#define NMax 100001
#define MMax 200001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
//////////////////////////////////////
typedef struct
{
    int x,y;
} muchie;
muchie g[MMax];
int c[NMax],n,m;
int nrComp;
/////////////////////////////////////
void citireInit();
void descompCompC();
void afisare();
/////////////////////////////////////
int main ()
{
    citireInit();
    descompCompC();
    afisare();
}
void citireInit()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>g[i].x>>g[i].y;
    for (i=1;i<=n;i++) c[i]=i;
}
void descompCompC()
{
    int i,j,minv,maxv;
    for (i=1;i<=n;i++) c[i]=i;
    for (i=1;i<=m;i++)
        if (c[g[i].x]!=c[g[i].y])
        {
            if (c[g[i].x]<c[g[i].y])
            {
                minv=c[g[i].x];
                maxv=c[g[i].y];
            }
            else
            {
                minv=c[g[i].y];
                maxv=c[g[i].x];
            }
            for (j=1;j<=n;j++)
                if (c[j]==maxv) c[j]=minv;
        }
}
void afisare ()
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        if (c[i])
        {
            nrComp++;
            for (j=i+1;j<=n;j++)
                if (c[j]==c[i]) c[j]=0;
        }
    }
    fout<<nrComp<<"\n";
}