Pagini recente » Cod sursa (job #144788) | Cod sursa (job #227317) | Cod sursa (job #2676724) | Cod sursa (job #2582883) | Cod sursa (job #766650)
Cod sursa(job #766650)
#include <iostream>
#include <fstream>
using namespace std;
#define nmax 101000
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M;
int viz[nmax];
class graf{
typedef struct nod{
int val;
nod *urm;
} *Pnod;
Pnod p[nmax];
public:
void add(int a, int b);
friend istream &operator>>(istream&, graf&);
void dfs(int nod);
};
void graf::add(int a, int b){
nod * c=new nod;
c->val=b;
c->urm=p[a];
p[a]=c;
}
istream &operator>>(istream &in, graf& G){
int a,b;
in>>N>>M;
while(M--){
in>>a>>b;
G.add(a,b);
G.add(b,a);
}
return in;
}
void graf::dfs(int nod){
if (viz[nod])
return ;
viz[nod]=1;
Pnod c;
c=p[nod];
while(c){
if (!viz[c->val]){
viz[c->val]=1;
dfs(c->val);
}
c=c->urm;
}
}
int main(){
graf G;
f>>G;
int ans=0;
for (int i=1;i<=N;++i)
if (!viz[i]){
ans++;
G.dfs(i);
}
g<<ans;
return 0;
}