Pagini recente » Cod sursa (job #2411961) | Cod sursa (job #2132627) | Cod sursa (job #301756) | Cod sursa (job #2218986) | Cod sursa (job #1599915)
#include <bitset>
#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 100003;
int N, M;
vector < int > v[MAXN];
bitset < MAXN > visited;
void readInput() {
ifstream fin("dfs.in");
fin >> N >> M;
for ( int i = 0; i < M; ++i ) {
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
fin.close();
}
void DFS( int node ) {
visited[node] = true;
vector < int > :: iterator it;
for ( it = v[node].begin(); it != v[node].end(); ++it )
if ( !visited[*it] )
DFS(*it);
/*
for ( int i = 0; i < v[node].size(); ++i ) {
int nextNode = v[node][i];
if ( !visited[nextNode] )
DFS( nextNode );
}
*/
}
void findSolution() {
int compConexe = 0;
for ( int i = 1; i <= N; ++i ) {
if ( !visited[i] ) {
DFS(i);
++compConexe;
}
}
ofstream fout("dfs.out");
fout << compConexe;
fout.close();
}
int main() {
readInput();
findSolution();
return 0;
}