Pagini recente » Cod sursa (job #2991030) | Cod sursa (job #3236223) | Cod sursa (job #1423533) | Cod sursa (job #105212) | Cod sursa (job #1130188)
#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";
}