Pagini recente » Cod sursa (job #397237) | Cod sursa (job #1577123) | Cod sursa (job #866039) | Cod sursa (job #412323) | Cod sursa (job #1445714)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <stack>
#include <vector>
#include <list>
using namespace std;
//#define _submit
#ifdef _submit
#define InFile "dfs.in"
#define OutFile "dfs.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif
class graph {
private:
vector< list<int> > adiac;
graph();
public:
const list<int>& getList(int);
graph(int);
void addEdge(int, int);
void DFS(int, vector<char>&);
int size();
int nrCompConex();
};
int graph::nrCompConex() {
vector<char> visited(size(), 0);
int nr = 0;
for (int i = 0; i < size(); i++)
if (!visited[i]) {
nr++;
DFS(i, visited);
}
return nr;
}
graph::graph(int nrnod) {
adiac.resize(nrnod);
}
const list<int>& graph::getList(int nod) {
return adiac[nod];
}
void graph::addEdge(int n1, int n2) {
adiac[n1].push_back(n2);
adiac[n2].push_back(n1);
}
int graph::size() {
return adiac.size();
}
void graph::DFS(int startNod, vector<char> &visited) {
stack<int> S;
S.push(startNod);
while (!S.empty()) {
int curNod = S.top();
S.pop();
if (visited[curNod])
continue;
visited[curNod] = 1;
const list<int>& vecini = getList(curNod);
for (auto i = vecini.begin(); i != vecini.end(); ++i)
if (!visited[*i])
S.push(*i);
}
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OutFile, "w", stdout));
int N, M;
scanf("%d%d", &N, &M);
graph *G = new graph(N);
while (M--) {
int n1, n2;
scanf("%d%d", &n1, &n2);
G->addEdge(n1-1, n2-1);
}
printf("%d\n", G->nrCompConex());
return 0;
}