Pagini recente » Cod sursa (job #1769867) | Cod sursa (job #3202852) | Cod sursa (job #1683602) | Cod sursa (job #822433) | Cod sursa (job #1168561)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream is("dfs.in");
ofstream os("dfs.out");
#define MAX 100001
int N, M, Sol, x, y;
vector <int> V[MAX];
bool d[MAX];
queue <int> Q;
void Input();
void DFS();
int main()
{
Input();
DFS();
os << Sol;
is.close();
os.close();
}
void Input()
{
is >> N >> M;
for ( int i = 1; i <= M; ++i )
{
is >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
}
void DFS()
{
for ( int i = 1; i <= N; ++i )
{
if ( d[i] == false )
{
++Sol;
Q.push(i);
while ( !Q.empty() )
{
for ( int j = 0; j < V[Q.front()].size(); ++j )
{
if ( d[V[Q.front()][j]] == 0 )
{
d[V[Q.front()][j]] = 1;
Q.push(V[Q.front()][j]);
}
}
Q.pop();
}
}
}
}