Pagini recente » Cod sursa (job #61314) | Cod sursa (job #1344647) | Cod sursa (job #863569) | Cod sursa (job #1250066) | Cod sursa (job #1493653)
#include <fstream>
using namespace std;
#define N 100005
#define M 200005
ifstream in("dfs.in");
ofstream out("dfs.out");
int lst[N], vf[2 * M], urm[2 * M];
int n, m, nr;
int stiva[N], nstiva;
bool ok[N];
int nrcomp;
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
vf[++nr] = x;
urm[nr] = lst[y];
lst[y] = nr;
}
for(int i = 1; i <= n; i++)
if(ok[i] == 0)
{
nrcomp++;
stiva[++nstiva] = i;
while(nstiva)
{
int x = stiva[nstiva--];
ok[x] = 1;
for(int j = lst[x]; j; j = urm[j])
{
int y = vf[j];
if(!ok[y])
stiva[++nstiva] = y;
}
}
}
out << nrcomp;
return 0;
}