Pagini recente » Cod sursa (job #585508) | Cod sursa (job #1665047) | Cod sursa (job #1580649) | Cod sursa (job #2214890) | Cod sursa (job #2924828)
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
int n;
int m;
int cc;
vector< vector<int> > graph;
vector<bool> seen;
vector<bool> inStack;
vector< pair<int, int> > backEdges;
vector< pair<int, int> > traverseEdges;
vector< pair<int, int> > advanceEdges;
void read() {
cin >> n >> m;
graph.resize(n + 1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
void dfs(int node) {
seen[node] = true;
inStack[node] = true;
for (int ngh: graph[node]) {
if (!seen[ngh]) {
advanceEdges.push_back(make_pair(node, ngh));
dfs(ngh);
}
else if (inStack[ngh]) {
backEdges.push_back(make_pair(node, ngh));
}
else {
traverseEdges.push_back(make_pair(node, ngh));
}
}
}
void print() {
cout << cc;
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
read();
seen.resize(n + 1);
inStack.resize(n + 1);
cc = 0;
for (int i = 1; i <= n; i++)
if (!seen[i]) {
cc++;
dfs(i);
}
print();
return 0;
}