Pagini recente » Cod sursa (job #2243407) | Cod sursa (job #2676864) | Cod sursa (job #1996320) | Cod sursa (job #2969202) | Cod sursa (job #1051774)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
#define nmax 100006
struct graph{
int node;
graph *next;
};
graph *gf[nmax];
int n, m;
bool viz[nmax];
void add(int x, int y){
graph *newNode = new graph;
newNode -> node = y;
newNode -> next = gf[x];
gf[x] = newNode;
}
void citeste(){
f >> n >> m;
for(int i=1; i<=m; ++i){
int x, y; f >> x >> y;
add(x, y);
add(y, x);
}
}
void dfs(int nod){
viz[nod] = 1;
for(graph *p=gf[nod]; p != NULL; p = p->next){
if (viz[ p->node ] == 0){
dfs( p->node );
}
}
}
void rezolva(){
int cntComp = 0;
for(int i=1; i<=n; ++i){
if (viz[i] == 0){
++cntComp;
dfs(i);
}
}
cout << cntComp << "\n";
g << cntComp << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}