Pagini recente » Cod sursa (job #1169545) | Cod sursa (job #1892944) | Cod sursa (job #2631343) | Cod sursa (job #2682525) | Cod sursa (job #2199631)
#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 = 1 ; i <= n ; i++)
if(!viz[i]) {
comp++ ;
dfs(i) ;
}
fout << comp ;
return 0 ;
}