Cod sursa(job #2007429)
| Utilizator | Data | 2 august 2017 21:06:17 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.6 kb |
#include <bits/stdc++.h>
#define nmax 100002
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
vector<int> G[nmax];
int N,M,V[nmax];
void DFS(int nod, int nr){
V[nod]=nr;
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
if(V[*it]==-1)DFS(*it,nr);
}
int main()
{
int a,b,n=0;
fin>>N>>M;
for(int i=1;i<=M;++i){
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
memset(V,-1,sizeof(V));
for(int i=1;i<=N;++i)
if(V[i]==-1)DFS(i,++n);
fout<<n<<endl;
return 0;
}
