Pagini recente » Cod sursa (job #2420929) | Cod sursa (job #2420924) | Cod sursa (job #2420928) | Cod sursa (job #2196589) | Cod sursa (job #2196567)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
void DFS(int node, vector<int> adj[], vector<int> &color) {
color[node] = 1;
for(int i = 0; i < adj[node].size(); i++) {
if(color[adj[node][i]] == 0) {
DFS(adj[node][i], adj, color);
}
}
color[node] = 2;
}
const int kNmax = 100005;
int main() {
int n;
int m;
int x,y;
int source;
vector<int> adj[kNmax];
vector<int> color;
ifstream fin("dfs.in");
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
}
color.push_back(-1);
for(int i = 1; i<=n;i++){
color.push_back(0);
}
int conex = 0;
for(int i = 1; i <= n; i++) {
if(color[i]==0){
DFS(i, adj, color);
conex++;
}
}
ofstream fout("dfs.out");
fout << conex;
fout.close();
fin.close();
}