Pagini recente » Cod sursa (job #2163198) | Cod sursa (job #1313587) | Cod sursa (job #2477710) | Cod sursa (job #625169) | Cod sursa (job #1198817)
//queue method
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream is ("dfs.in");
ofstream os ("dfs.out");
int N, M, sol;
vector <int> nod[100002];
bool marked[100002];
queue <int> Q;
void Read();
void DFS();
int main()
{
Read();
DFS();
is.close();
os.close();
}
void Read()
{
is >> N >> M;
int a, b;
for (int i = 0; i < M; ++i)
{
is >> a >> b;
nod[a].push_back(b);
nod[b].push_back(a);
}
};
void DFS()
{
for (int i = 1; i <= N; ++i)
{
if (marked[i] == false)
{
++sol;
Q.push(i);
for (; !Q.empty(); Q.pop())
{
for (int j = 0; j < nod[Q.front()].size(); ++j)
{
if (marked[nod[Q.front()][j]] == 0)
{
marked[nod[Q.front()][j]] = 1;
Q.push(nod[Q.front()][j]);
}
}
}
}
}
os << sol;
};