Pagini recente » Cod sursa (job #1520695) | Cod sursa (job #2834417) | Cod sursa (job #1942925) | Cod sursa (job #1888588) | Cod sursa (job #2956963)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
using namespace std;
class Graph{
int n, m;
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<int> father;
std::vector<int> distance;
std::vector<bool> visited;
std::stack<int> s;
int totalCost;
void dfs(const int k){
visited[k] = true;
for (int node : getNeighbors(k)){
if ( !visited[node] ){
father[node] = k;
dfs(node);
}
}
s.push(k);
}
void bfs(const int start){
std::queue<int> q;
q.push(start);
visited[start] = true;
distance[start] = 0;
while (!q.empty()){
int node = q.front();
q.pop();
for (int neighbor : getNeighbors(node)){
if (!visited[neighbor]){
visited[neighbor] = true;
distance[neighbor] = distance[node] + 1;
father[neighbor] = node;
q.push(neighbor);
}
}
}
}
struct edge{
int cost, x, y;
bool operator<(const edge o) const{
return ((this->cost) > o.cost);
}
};
void dijkstra(const int start){
distance.assign(n+1, 0x7fffffff);
std::queue<std::pair<int, int>> q;
q.push({0, start});
distance[start] = 0;
while (!q.empty()){
int currentNode = q.front().second;
q.pop();
for (const auto &node : getNeighborsWithWeight(currentNode)){
if(distance[currentNode] + node.second < distance[node.first])
{
distance[node.first] = distance[currentNode] + node.second;
q.push({-distance[node.first], node.first});
}
}
}
}
public:
explicit Graph(const int n = 0){
this -> n = n;
totalCost = m = 0;
graph.resize(n+1);
father.resize(n+1);
distance.resize(n+1);
visited.resize(n+1);
}
void addEdge(const int x, const int y, const int cost = 1){
graph[x].push_back({y, cost});
++m;
}
int getEdgeWeight(const int x, const int y) const {
for (const auto& neighbor : graph[x]) {
if (neighbor.first == y) {
return neighbor.second;
}
}
return (int)0x80000000;
}
std::vector<int> getNeighbors(const int x) const {
std::vector<int> neighbors;
for (const auto& neighbor : graph[x]) {
neighbors.push_back(neighbor.first);
}
return neighbors;
}
std::vector<std::pair<int, int>> getNeighborsWithWeight(const int x) const {
return graph[x];
}
std::stack<int> topologicalSort() {
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i);
}
}
visited.assign(n+1, false);
return s;
}
void removeEdge(const int x, const int y){
for (auto it = graph[x].begin(); it != graph[x].end(); ++it) {
if (it -> first == y) {
graph[x].erase(it);
--m;
return;
}
}
}
void removeNode(const int x){
for (int i = 1; i <= n; ++i) {
removeEdge(i, x);
removeEdge(x, i);
}
graph[x].clear();
--n;
}
std::vector<std::pair<int, int>> MST(int x){
std::vector<std::pair<int, int>> mst;
visited.assign(n+1, false);
visited[x] = true;
std::priority_queue<edge> q;
for(auto e : getNeighborsWithWeight(x)) {
edge V{e.second, x, e.first};
q.push(V);
}
while (!q.empty()){
edge k = q.top();
q.pop();
if(visited[k.y] == 0) {
mst.push_back({k.x, k.y});
totalCost += k.cost;
visited[k.y] = true;
for (auto e: graph[k.y]) {
edge V{e.second, k.y, e.first};
q.push(V);
}
}
}
return mst;
}
int getCost() const {
return totalCost;
}
int getShortestPathFromTo(const int from, const int to){
dijkstra(from);
return distance[to];
}
std::vector<int> getDistancesFrom(const int from){
dijkstra(from);
return distance;
}
int howManyCC(){
int count = 0;
visited.assign(false, n+1);
for(int i = 1; i <= n; ++i){
if ( !visited[i] ){
++count;
dfs(i);
}
}
return count;
}
};
int main() {
ifstream in("dfs.in");
int n, m;
in >> n >> m;
Graph g(n);
while (m--){
int x, y;
in >> x >> y;
g.addEdge(y, x);
g.addEdge(x, y);
}
in.close();
ofstream out("dfs.out");
out << g.howManyCC();
out.close();
return 0;
}