Pagini recente » Cod sursa (job #329226) | Cod sursa (job #1825890) | Cod sursa (job #1848363) | Cod sursa (job #3249027) | Cod sursa (job #1235199)
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>
using namespace std;
const char infile[] = "dfs.in";
const char outfile[] = "dfs.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXN = 100005;
const int oo = 0x3f3f3f3f;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
class DirectedGraph {
private:
vector <vector <int> > G;
public:
DirectedGraph() {
}
DirectedGraph(int _N) {
G.resize(_N);
}
void addDirectedEdge(int x, int y) {
G[x].push_back(y);
}
void addUndirectedEdge(int x, int y) {
G[x].push_back(y);
G[y].push_back(x);
}
void dfs(int node, vector <bool>& used) {
used[node] = 1;
for(auto it: G[node])
if(!used[it])
dfs(it, used);
}
int getConnectedComponents() {
int ans = 0;
vector <bool> used(G.size(), 0);
for(int i = 0 ; i < G.size() ; ++ i)
if(!used[i]) {
++ ans;
dfs(i, used);
}
return ans;
}
vector <int> bfs(int Source) {
vector <int> dist(G.size(), -1);
queue <int> Q;
Q.push(Source);
dist[Source] = 0;
while(!Q.empty()) {
int node = Q.front();
Q.pop();
for(auto it: G[node])
if(dist[it] == -1) {
dist[it] = dist[node] + 1;
Q.push(it);
}
}
return dist;
}
};
int N, M, Source;
int main() {
fin >> N >> M;
DirectedGraph G(N);
for( ; M -- ; ) {
int x, y;
fin >> x >> y;
-- x ; -- y;
G.addUndirectedEdge(x, y);
}
fout << G.getConnectedComponents() << '\n';
fin.close();
fout.close();
return 0;
}