Mai intai trebuie sa te autentifici.
Cod sursa(job #1973702)
| Utilizator | Data | 25 aprilie 2017 18:54:50 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 80 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.86 kb |
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("dfs.in" );
ofstream out("dfs.out");
vector<int>ha[100000];
int v[200001],hz[200001];
int n,m,i,st,dr,a,b,j,sol;
int main(){
in >> n;
in >> m;
for( i = 1; i <= m; i ++ ){
in >> a >> b;
ha[a].push_back(b);
ha[b].push_back(a);
}
for( j = 1; j <= n; j ++ ){
if( hz[j] == 0 ){
sol ++;
v[1] = j;
hz[j] = 1;
for( st = 1,dr = 1; st <= dr; st ++ ){
for( i = 0; i < ha[v[st]].size(); i ++ ){
if( hz[ ha[v[st]][i] ] == 0 ){
dr ++;
v[dr] = ha[v[st]][i];
hz[ha[v[st]][i] ] = 1;
}
}
}
}
}
out<<sol;
return 0;
}
