Pagini recente » Cod sursa (job #2645049) | Cod sursa (job #217770) | Cod sursa (job #2250427) | Cod sursa (job #115599) | Cod sursa (job #2919302)
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph{
private:
int n_nodes;
vector<vector<int>> adj;
vector<pair< int , pair<int,int>> > adj_weight;
public:
Graph(){
n_nodes = 0;
adj = {};
}
Graph(int n, vector<vector<int>> &gr){
n_nodes = n;
adj = gr;
}
void dfs(int node, vector<bool> &visited, vector<vector<int>> &gr);
void dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution);
void dfs_comp_conexe(int node, vector<bool> &visited, vector<vector<int>> &gr, int &cnt);
void solve_sort_top();
void solve_comp_conexe();
};
void Graph:: dfs(int node, vector<bool> &visited, vector<vector<int>> &gr){
visited[node] = true;
for(auto &x: gr[node]){
if(!visited[x]) dfs(x, visited, gr);
}
}
void Graph:: dfs_comp_conexe(int node, vector<bool> &visited, vector<vector<int>> &gr, int &cnt){
visited[node] = true;
for(auto &x: gr[node]){
if(!visited[x]) dfs(x, visited, gr);
}
cnt++;
}
void Graph:: dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution){
visited[node] = true;
for(auto &x: gr[node]){
if(!visited[x]) dfs_sort_top(x, visited, gr, solution);
}
solution.push_back(node);
}
void Graph::solve_sort_top(){
vector<bool> v(n_nodes+1, false);
vector<int> sol(n_nodes+1);
for(int i = 1; i <= n_nodes; ++i){
if(!v[i]) dfs_sort_top(i, v, adj, sol);
}
reverse(sol.begin(), sol.end());
for(int i = 0; i < n_nodes; ++i)
//cout<<sol[i]<<' ';
fout<<sol[i]<<' ';
}
void Graph::solve_comp_conexe(){
vector<bool> v(n_nodes+1, false);
vector<int> sol(n_nodes+1);
int ans = 0;
for(int i = 1; i <= n_nodes; ++i){
if(!v[i]) dfs_comp_conexe(i, v, adj, ans);
}
fout<<ans<<' ';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, x, y;
// cin>>n>>m;
fin>>n>>m;
vector<vector<int>> aux(n+1);
for(int i = 0; i < m; ++i){
// cin>>x>>y;
fin>>x>>y;
aux[x].push_back(y);
}
Graph g = Graph(n, aux);
g.solve_comp_conexe();
return 0;
}