Pagini recente » Cod sursa (job #2985207) | Cod sursa (job #1854061) | Borderou de evaluare (job #2037265) | Cod sursa (job #2161865) | Cod sursa (job #3262701)
#include <bits/stdc++.h>
using namespace std;
#define inFile "dfs.in"
#define outFIle "dfs.out"
FILE *in = fopen(inFile, "r");
FILE *out = fopen(outFIle, "w");
#define maxSize 100002
#define inf INT_MAX
vector <int> adj[maxSize];
bitset <maxSize> visited;
void depthSearch(int curNode) {
for (auto curNeibor : adj[curNode]) {
if (visited[curNeibor]) continue ;
visited[curNeibor] = true;
depthSearch( curNeibor );
}
}
int main( ) {
int numNodes, numEdges; fscanf(in, "%d %d", &numNodes, &numEdges);
int nodeA, nodeB;
for (int i = 0; i < numEdges; ++i) {
fscanf(in, "%d %d", &nodeA, &nodeB);
adj[nodeA].push_back( nodeB );
adj[nodeB].push_back( nodeA );
}
int numComponents = 0;
for (int curNode = 1; curNode <= numNodes; ++curNode)
if (!visited[curNode]) {
++numComponents;
depthSearch( curNode );
}
fprintf(out, "%d\n", numComponents);
return 0;
}