Pagini recente » Cod sursa (job #3315302) | Cod sursa (job #3316858) | Cod sursa (job #3313555) | Cod sursa (job #629189) | Cod sursa (job #3318568)
// DFS
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
vector <int> L[100001];
int viz[100001];
int n, m,x,y,i,j,cc;
void DFS(int nod)
{
viz[nod]=1;
for (int i=0 ; i<L[nod].size(); i++)
{
if(viz[L[nod][i]]==0)
DFS(L[nod][i]);
}
}
int main(){
cin>>n>>m;
for( i=1; i<=m; i++)
{
cin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
// for(i=1;i<=n;i++)
// {
// cout<<i<<": ";
// for( j = 0; j<L[i].size() ; j++)
// cout<<L[i][j]<< " ";
// cout<<endl;
// }
cc=0;
for(i=1 ;i<= n; i++)
{
if(viz[i]==0)
{
DFS(i);
cc++;
}
}
cout<<cc;
return 0;
}