Cod sursa(job #1723230)
Utilizator | Data | 30 iunie 2016 03:30:56 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int>f[100001];
int k,i,m,x,j,ct;
bool g[100001];
void DFS(int x)
{
int k,i,m;
g[x]=1;
for(k=0;k<f[x].size();k++)
{
if(!g[f[x][k]])
DFS(f[x][k]);
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&x,&m);
for(k=1;k<=m;k++)
{
scanf("%d%d",&i,&j);
f[i].push_back(j);
f[j].push_back(i);
}
for(k=1,i=0;k<=x;k++)
{
if(!g[k])
{
DFS(k);
i++;
}
}
printf("%d\n",i);
return 0;
}