Pagini recente » Cod sursa (job #2642473) | Cod sursa (job #1060601) | Cod sursa (job #1228407) | Cod sursa (job #3033125) | Cod sursa (job #605394)
Cod sursa(job #605394)
# include <cstdio>
# include <queue>
# include <vector>
using namespace std;
const char *FIN = "dfs.in", *FOU = "dfs.out";
const int MAX = 100005;
int N, M, sol, VIZ[MAX];
vector <int> G[MAX];
void dfs (int S) {
VIZ[S] = 1;
for (vector <int> :: iterator it = G[S].begin (); it != G[S].end (); ++it)
if (VIZ[*it] == 0)
dfs (*it);
}
void bfs (int S) {
VIZ[S] = 1;
queue <int> Q;
for (Q.push (S); !Q.empty (); Q.pop ()) {
int X = Q.front ();
for (vector <int> :: iterator i = G[X].begin (); i != G[X].end (); ++i)
if (VIZ[*i] == 0) {
Q.push (*i), VIZ[*i] = 1;
}
}
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d %d", &N, &M);
for (int i = 1, x, y; i <= M; ++i) {
scanf ("%d %d", &x, &y);
G[x].push_back (y);
G[y].push_back (x);
}
for (int i = 1; i <= N; ++i)
if (VIZ[i] == 0)
++sol, bfs (i);
fprintf (fopen (FOU, "w"), "%d", sol);
}