Pagini recente » Cod sursa (job #3368134) | Cod sursa (job #3368059) | Cod sursa (job #3368104) | Cod sursa (job #3368070) | Cod sursa (job #3368131)
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <stack>
#include <fstream>
using namespace std;
struct Nod {
int n = -1;
vector<int> Adj;
};
struct Graph {
vector<Nod> Nodes;
int edgeCount = 0;
void SetNodeCount(int n) {
Nodes.resize(n);
for (int i = 0; i < n; i++) {
Nodes[i].n = i;
}
}
int GetNodeCount() {
return Nodes.size();
}
Nod& operator[] (int i) {
return Nodes[i];
}
void AddEdge(int u, int v) {
Nodes[u].Adj.push_back(v);
edgeCount++;
}
int GetEdgeCount() const {
return edgeCount;
}
};
vector<int> bfs(Graph &G, int S) {
vector<int> res(G.GetNodeCount(), -1);
queue<int> Q;
Q.push(S);
res[S] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i : G[u].Adj) {
if (res[i] == -1) {
Q.push(i);
res[i] = res[u] + 1;
}
}
}
return res;
}
int dfs(Graph &G) {
vector<bool> vis(G.GetNodeCount(), false);
stack<int> S;
int n = 0;
for (int i = 0; i < G.GetNodeCount(); i++) {
if (vis[i]) {
continue;
}
S.push(i);
vis[i] = true;
n++;
while (!S.empty()) {
int u = S.top();
S.pop();
for (int i : G[u].Adj) {
if (!vis[i]) {
S.push(i);
vis[i] = true;
}
}
}
}
return n;
}
pair<int, int> grarb(Graph &G) {
int AddCount = -1;
int RemoveCount = 0;
int M = G.GetEdgeCount();
int N = G.GetNodeCount();
int C = dfs(G);
RemoveCount = M - N + dfs(G);
AddCount = C - 1;
return make_pair(RemoveCount, AddCount);
}
vector<int> berarii2(Graph &G, vector<int> &B) {
vector<bool> vis(G.GetNodeCount(), false);
queue<int> Q;
for (auto b : B) {
Q.push(b);
vis[b] = true;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i : G[u].Adj) {
if (!vis[i]) {
Q.push(i);
vis[i] = true;
}
}
}
}
vector<int> res;
for (int i = 0; i < G.GetNodeCount(); i++) {
if (!vis[i]) {
res.push_back(i);
}
}
return res;
}
#define in fin
#define out fout
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int main() {
Graph G;
int N, M;
in >> N >> M;
G.SetNodeCount(N);
while (M--) {
int u, v;
in >> u >> v;
G.AddEdge(u-1, v-1);
}
cout << dfs(G);
//auto k = grarb(G);
//out << k.first << endl << k.second << endl;
}