Pagini recente » Cod sursa (job #2194285) | Cod sursa (job #719570) | Cod sursa (job #2160660) | Cod sursa (job #886178) | Cod sursa (job #1417289)
#include <fstream>
#include <cstring>
#define nmax 100001
using namespace std;
struct Nod {
int nd;
Nod *next;
};
Nod *G[nmax];
void getData(Nod *G[nmax],int &n,int &m) {
ifstream r("dfs.in");
r>>n>>m;
for (int k=1;k<=m;k++){
int i,j;
Nod *p;
r>>i>>j;
p=new Nod;
p->next=G[i];
p->nd=j;
G[i]=p;
p=new Nod;
p->next=G[j];
p->nd=i;
G[j]=p;
}
r.close();
}
void dfs(int x,bool (&viz)[nmax]) {
Nod *p;
viz[x]=true;
p=G[x];
while (p) {
if (!viz[p->nd])
dfs(p->nd,viz);
p=p->next;
}
}
int nrComp(Nod *G[nmax],int n) {
int nr=0,i;
bool viz[nmax];
memset(viz,false,sizeof(viz));
for(i=1;i<=n;i++)
if (!viz[i]){
nr++;
dfs(i,viz);
}
return nr;
}
void print(int x) {
ofstream w("dfs.out");
w<<x<<endl;
w.close();
}
int main () {
int n,m;
getData(G,n,m);
print(nrComp(G,n));
return 0;
}