Pagini recente » Cod sursa (job #1998141) | Cod sursa (job #3285783) | Cod sursa (job #925844) | Cod sursa (job #1350566) | Cod sursa (job #1705740)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
long N, M, nr;
bool visited[100001];
int main () {
FILE* input = fopen("dfs.in", "r");
FILE* output = fopen("dfs.out", "w");
fscanf(input, "%ld %ld", &N, &M);
vector< vector<long> > adjList(N+1, vector<long>());
long u, v;
for (long i = 0; i < M; i++) {
fscanf(input, "%ld %ld", &u, &v);
adjList[u].push_back(v);
}
for (long i = 1; i <= N; i++) {
stack<long> S;
if (!visited[i]){
S.push(i);
visited[i] = true;
while (!S.empty()) {
long s = S.top();
S.pop();
for (unsigned long j = 0; j < adjList[s].size(); j++) {
if (!visited[adjList[s][j]]) {
S.push(adjList[s][j]);
visited[adjList[s][j]] = true;
}
}
}
nr++;
}
}
fprintf(output, "%ld", nr);
fclose(input);
fclose(output);
return 0;
}