Pagini recente » Cod sursa (job #369481) | Cod sursa (job #388010) | Cod sursa (job #1528970) | Cod sursa (job #329313) | Cod sursa (job #1182134)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define DMAX 100001
struct Graph{
char inf[DMAX]; // content
char color[DMAX]; // w->g->b
int parent[DMAX], d[DMAX], f[DMAX]; // d = discovered, f = finished
vector<int> Adj[DMAX]; // Adj list
vector<pair<int, int>> Edge;
} G;
int N, M, timp, nrC;
void DFS_VISIT(int root){
int i, lg, next;
timp++;
G.color[root] = 'g';
G.d[root] = timp;
lg = G.Adj[root].size();
for (i = 0; i < lg; i++){
next = G.Adj[root][i];
if (G.color[next] == 'w')
DFS_VISIT(next);
}
timp++;
G.color[root] = 'b';
G.f[root] = timp;
}
void DFS(){
int i;
for (i = 1; i <= N; i++){
G.color[i] = 'w';
G.parent[i] = 0;
}
for (i = 1; i <= N; i++){
if (G.color[i] == 'w'){
nrC++;
DFS_VISIT(i);
}
}
}
int main(){
int i, ui, vi;
fin >> N;
//for (i = 1; i <= N; i++) fin >> G.inf[i];
fin >> M;
for (i = 0; i < M; i++) {
fin >> ui >> vi;
G.Adj[ui].push_back(vi);
G.Adj[vi].push_back(ui);
G.Edge.push_back(make_pair(ui, vi));
}
DFS();
fout << nrC;
return 0;
}