Pagini recente » Cod sursa (job #139143) | Cod sursa (job #556297) | Cod sursa (job #886778) | Cod sursa (job #1530276) | Cod sursa (job #1108310)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
#define NMAX 100000
ifstream in;
ofstream out;
vector<int> graph[NMAX];
bool graphVisited[NMAX];
void dfs(int node);
int main(int argc, char *argv[])
{
in.open("dfs.in");
out.open("dfs.out");
memset(graphVisited, false, sizeof(graphVisited));
int n, m;
in >> n >> m;
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
graph[aux1].push_back(aux2);
graph[aux2].push_back(aux1);
}
int connCount = 1;
for (int i = 0; i < m; i++) {
if (!graphVisited[i]){
dfs(i);
connCount++;
}
}
out << connCount;
in.close();
out.close();
return 0;
}
void dfs(int node)
{
if (graphVisited[node])
return;
else {
graphVisited[node] = true;
int n = graph[node].size();
for (int i = 0; i < n; i++)
dfs(graph[node].at(i));
}
}