Pagini recente » Cod sursa (job #1879062) | Cod sursa (job #2470871) | Cod sursa (job #2744975) | Cod sursa (job #2965069) | Cod sursa (job #2199624)
#include <fstream>
using namespace std;
ifstream fin ("dfs.in") ;
ofstream fout ("dfs.out") ;
const int N = 100001 ;
const int M = 200001 ;
int m , n , nr , lst[N] , vf[2*M] , urm[2*M] , viz[N] , comp ;
void adauga(int x , int y) {
vf[++nr] = y ;
urm[nr] = lst[x] ;
lst[x] = nr ;
}
void dfs (int x) {
viz[x] = comp ;
int p = lst[x] , y ;
while (p != 0) {
y = vf[p] ;
if ( !viz[y]) {
dfs(y) ;
}
p = urm[p] ;
}
}
int main()
{
fin >> n >> m ;
int x , y ;
for ( int i = 0 ; i < m ; i++) {
fin >> x >> y ;
adauga (x , y) ;
adauga ( y , x) ;
}
for(int i = 0 ; i < n ; i++)
if(!viz[i]) {
comp++ ;
dfs(i) ;
}
fout << comp ;
return 0 ;
}