Pagini recente » Statistici Teodor Rusu (teodorintai) | Cod sursa (job #1444137) | Istoria paginii runda/minune7/clasament | Cod sursa (job #2169449) | Cod sursa (job #1734574)
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;
void get_data (int &n_nodes, int &n_edges, vector <int> edges[nmax]){
ifstream fin ("dfs.in");
fin >> n_nodes >> n_edges;
for (int i = 1; i <= n_edges; i++){
int node_1, node_2;
fin >> node_1 >> node_2;
edges[node_1].push_back (node_2);
}
}
void dfs (int current_node, vector <int> edges[nmax], bool seen[nmax]){
seen[current_node] = true;
for (auto x : edges[current_node])
if (!seen[x])
dfs (x, edges, seen);
}
void print_data (int n_nodes, vector <int> edges[nmax]){
ofstream fout ("dfs.out");
bool seen[nmax];
for (int i = 1; i <= n_nodes; i++)
seen[i] = false;
int n_components = 0;
for (int i = 1; i <= n_nodes; i++)
if (!seen[i]){
dfs (i, edges, seen);
n_components ++;
}
fout << n_components;
}
int main(){
int n_nodes, n_edges;
vector <int> edges[nmax];
get_data (n_nodes, n_edges, edges);
print_data (n_nodes, edges);
}