Pagini recente » Cod sursa (job #2529985) | Cod sursa (job #2389304) | Cod sursa (job #1357397) | Cod sursa (job #1273839) | Cod sursa (job #2254954)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream inp("bfs.in");
ofstream out("bfs.out");
vector<int> G[NMAX];
int n, m, c, viz[NMAX];
void DFS(int nod)
{
viz[nod] = 1;
int nrnod = G[nod].size();
int nodc;
for(int i = 0; i < nrnod; ++i)
{
nodc = G[nod][i];
if(viz[nodc] == 0)
DFS(nodc);
}
}
int main()
{
inp >> n >> m;
int x, y;
for(int i = 1; i <= m; i++) {
inp >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int nod = 1; nod <= n; nod++)
if(viz[nod] == 0)
{
c++;
DFS(nod);
}
out << c;
}
/*#include <iostream>
#include <stdio.h>
#define NMAX 20000
#define MMAX 20000
using namespace std;
int n, m;
int a[NMAX][MMAX];
int viz[NMAX];
void DFS(int nod)
{
viz[nod] = 1;
for(int i = 1; i <= n; i++)
if(viz[i] != 1 && a[nod][i] != 0)
DFS(i);
}
int main()
{
freopen("bfs.in", "r", stdin);
freopen("bfs.out", "w", stdout);
scanf("%d %d", &n, &m);
int i, x, y;
for(i = 1; i <= n; ++i)
{
scanf("%d %d", &x, &y);
a[x][y] = a[y][x] = 1;
}
int comp = 0;
for(i = 1; i <= n; ++i)
if(viz[i] != 1)
{
comp++;
DFS(i);
}
printf("%d", comp);
return 0;
}*/