Pagini recente » Cod sursa (job #1742468) | Cod sursa (job #2122960) | Cod sursa (job #1687702) | Cod sursa (job #1350257) | Cod sursa (job #2789680)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
class Graph {
private:
struct Edge {
int x, y, cost;
Edge(int x, int y, int cost = 0) : x(x), y(y), cost(cost) {}
};
struct Neighbour {
int node, cost;
Neighbour(int x, int cost = 0) : node(x), cost(cost) {}
};
std::vector<std::vector<Neighbour> >la;
std::vector<Edge> edges;
const int N_NODES;
const int N_EDGES;
public:
Graph(int N, int M) : N_NODES(N), N_EDGES(M) { la.resize(N + 1); }
void getInfo();
void addEdge(int from, int to, int cost = 0,bool isDirected = 0);
std::vector<int> BFS(int start);
int getComponentCount();
};
void Graph::addEdge(int from, int to, int cost, bool isDirected) {
la[from].push_back({ to, cost });
edges.push_back({ from, to, cost });
if (!isDirected) {
la[to].push_back({ from, cost });
}
}
std::vector<int> Graph::BFS(int start) {
std::vector<int> dist(N_NODES + 1, -1);
dist[start] = 0;
std::queue<int> q;
q.push(start);
while (!q.empty()) {
int top = q.front();
q.pop();
for (const Neighbour& x : la[top]) {
if (dist[x.node] == -1) {
dist[x.node] = dist[top] + 1;
q.push(x.node);
}
}
}
return std::vector<int>(dist.begin() + 1, dist.end());
}
int Graph::getComponentCount() {
std::stack<int> st;
std::vector<bool> used(N_NODES + 1, false);
int count = 0;
for (int i = 1; i <= N_NODES; ++i) {
if (!used[i]) {
count++;
// DFS
st.push(i);
while (!st.empty()) {
int top = st.top();
st.pop();
used[top] = 1;
for (const Neighbour& n : la[top])
if (!used[n.node]) st.push(n.node);
}
}
}
return count;
}
void Graph::getInfo() {
std::cout << "N: " << N_NODES << '\n';
std::cout << "M: " << N_EDGES << '\n';
for (int i = 1; i <= N_NODES; ++i) {
std::cout << i << ": ";
for (const Neighbour& x : la[i]) {
std::cout << "(" << x.node << ", " << x.cost << ") ";
}
std::cout << '\n';
}
std::cout << "Edges: \n";
for (const Edge& m : edges) {
std::cout << m.x << " " << m.y << " " << m.cost << '\n';
}
}
int main(){
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
int N, M;
f >> N >> M;
Graph a(N, M);
for (int i = 0; i < M; ++i) {
int x, y;
f >> x >> y;
a.addEdge(x, y);
}
g << a.getComponentCount();
}