Pagini recente » Cod sursa (job #226884) | Cod sursa (job #2355324) | Cod sursa (job #1953036) | Cod sursa (job #1065812) | Cod sursa (job #1098390)
#include <cstdio>
#define Nmax 100002
#define Mmax 2*Nmax
using namespace std;
struct nod
{
int x;
nod *urm;
}*G[Nmax];
FILE *fi = fopen("dfs.in", "r");
FILE *fo = fopen("dfs.out", "w");
int viz[Nmax];
int nrc = 0;
int n;
int m;
void adauga(int x, int y)
{
nod *q = new nod;
q->x = y;
q->urm = 0;
if (!G[x])
{
G[x] = q;
}
else if (G[x]->x > y)
{
q->urm = G[x];
G[x] = q;
}
else
{
nod *p;
nod *r;
for (p = G[x]; p && p->x < y; r=p, p=p->urm);
r->urm = q;
if (p) r->urm = q;
}
}
void citire()
{
int x, y;
fscanf(fi, "%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
fscanf(fi, "%d%d", &x, &y);
adauga(x, y);
adauga(y, x);
}
}
void DF(int x)
{
viz[x] = 1;
for (nod *p=G[x]; p; p=p->urm)
if (!viz[p->x])
DF(p->x);
}
int main()
{
citire();
for (int i=1; i<=n; i++)
if (!viz[i])
{
++nrc;
DF(i);
}
fprintf(fo, "%d", nrc);
return 0;
}