Pagini recente » Cod sursa (job #1290617) | Cod sursa (job #1700860) | Cod sursa (job #2283869) | Cod sursa (job #1300020) | Cod sursa (job #2786014)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph {
private:
int nodes, edges, starting_node,dfs_time;
int *color; //3 color 0 -> white, 1 -> gray, 2 -> black
int *distances;
int *visited;
pair<int,int>* times;
vector<int> *preds; //not using yet
vector<int> *adjacency_list;
bool oriented;
public:
Graph(int nodes = 0, int edges = 0, int starting_node = 0, bool oriented = true) :
nodes(nodes), edges(edges), oriented(oriented), starting_node(starting_node) {
dfs_time = 0;
color = (int *) calloc(nodes + 1, sizeof(int));
distances = (int *) calloc(nodes + 1, sizeof(int));
times = (pair<int,int>*)calloc(nodes + 1, sizeof (pair<int,int>));
preds = new vector<int>[nodes + 1];
adjacency_list = new vector<int>[nodes + 1];
visited = (int *) calloc(nodes + 1, sizeof(int));
}
~Graph() {
free(color);
free(distances);
free(visited);
free(times);
delete[] preds;
delete[] adjacency_list;
}
void get_times(){
for(int i = 1;i<nodes+1;i++){
cout << times[i].first << ' ' << times[i].second;
cout<<'\n';
}
}
int getNodes() const {
return nodes;
}
void setNodes(int nodes) {
nodes = nodes;
}
int getEdges() const {
return edges;
}
void setEdges(int edges) {
edges = edges;
}
bool isOriented() const {
return oriented;
}
void setOriented(bool oriented) {
Graph::oriented = oriented;
}
void set_graph() {
int x, y;
if (isOriented()) {
for (int i = 1; i <= edges; i++) {
fin >> x >> y;
adjacency_list[x].push_back(y);
}
} else {
for (int i = 1; i <= edges; i++) {
fin>>x>>y;
adjacency_list[x].push_back(y);
adjacency_list[y].push_back(x);
}
}
}
void show_graph() {
for (int i = 1; i <= nodes; i++) {
cout << i << ":";
for (int neighbor : adjacency_list[i]) {
cout << neighbor << ' ';
}
cout << '\n';
}
}
void show_distances() {
BFS();
for (int i = 1; i < nodes + 1; i++) {
fout << distances[i] - 1 << ' ';
}
}
void conex_components(){
int cnt = 0;
for(int i = 1;i<nodes+1;i++){
if(!visited[i]) {
DFS(i);
cnt++;
}
}
fout<<cnt;
}
private:
void BFS() {
queue<int> que;
que.push(starting_node);
visited[starting_node] = 1;
color[starting_node] = 1;
distances[starting_node] = 1;
while (!que.empty()) {
int node = que.front();
que.pop();
for (int neighbor : adjacency_list[node]) {
if (color[neighbor] == 0) {
que.push(neighbor);
color[neighbor] = 1;
visited[neighbor] = 1;
distances[neighbor] = distances[node] + 1;
}
}
color[node] = 2;
}
}
void DFS(int start = 1) {
dfs_time += 1;
times[start].first = dfs_time;
color[start] = 1;
visited[start] = 1;
for(int neighbor : adjacency_list[start]){
if(!visited[neighbor]){
DFS(neighbor);
}
}
color[start] = 2;
dfs_time+=1;
times[start].second = dfs_time;
}
};
int main() {
int n, m;
fin >> n >> m;
Graph g(n, m, 0, false);
g.set_graph();
g.conex_components();
return 0;
}