Pagini recente » Cod sursa (job #2719175) | Cod sursa (job #583263) | Cod sursa (job #1033016) | Cod sursa (job #3254592) | Cod sursa (job #1726563)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
vector <int> v[100005];
int a[100005];
int n, m, cc, x, y, i, j;
void dfs(int node) {
a[node] = cc;
for (size_t i = 0; i < v[node].size() ;++i) {
int x = v[node][i];
if (a[x] == 0) {
dfs(x);
}
}
}
int main ()
{
f>>n>>m;
for (i=1; i<=m; i++)
{
f>>x>>y;
v[ x ].push_back(y);
v[ y ].push_back(x);
}
for (i=1; i<=n; i++)
{
if (a[i]==0)
{
cc++;
dfs(i);
}
/* queue<int> q;
q.push(i);
while (!q.empty()) {
x = q.front();
a[x] = cc;
q.pop();
for (j = 0; j < int(v[x].size()); ++j) {
y = v[x][j];
if (a[y] == 0) {
q.push(y);
}
}
}
*/
}
g << cc;
return 0;
}