Pagini recente » Cod sursa (job #1019230) | Cod sursa (job #1129307) | Cod sursa (job #1513067) | Cod sursa (job #634882) | Cod sursa (job #2422942)
#include <iostream>
//DFS- nr de componente conexe dintr un graf
#include <fstream>
#include <vector>
#define NMAX 100100
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int viz[100100];
vector <int> graf[NMAX];
void DFS(int nod)
{
viz[nod] = 1;
//cout<<nod<<" ";
//cout<<graf[nod].size();
for(int i=0; i<graf[nod].size(); i++)
{
int vecin = graf[nod][i];
if(viz[vecin]==0) DFS(vecin);
}
}
int main()
{
int n,m,a,b;
f>>n; //nr noduri;
f>>m; //nr muchii;
for(int i=1; i<=m; i++)
{
f>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);//graf neorientat
}
for(int i=1;i<=n;i++)
viz[i] = 0;
int answer = 0;
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
{//
answer++;
DFS(i);
//cout<<endl;
}
}
//DFS(1);
//cout<<"graful are "<<answer<<" componente conexe"<<endl;
g<<answer;
return 0;
}