Pagini recente » simulare_republicana_2 | concurs_1 | Istoria paginii runda/eusebiu_oji_2013_cls10 | Cod sursa (job #1901074) | Cod sursa (job #216103)
Cod sursa(job #216103)
// dfs-componente conexe vector<int> stl
using namespace std;
#include <cstdio>
#include <vector>
#define N 100001
#define pb push_back
vector<int> a[N];
int n,m;
bool use[N];
void read()
{
freopen("dfs.in","r",stdin);
scanf("%d %d\n", &n, &m);
int p, q;
while(m--)
{
scanf("%d %d\n", &p,&q);
a[p].pb(q);
a[q].pb(p);
}
}
inline void dfs(int n)
{
use[n]=1;
for(vector<int>::iterator it=a[n].begin(); it!=a[n].end(); ++it)
if(!use[*it])
dfs(*it);
}
int main()
{
read();
int i, sol=0;
for(i=1;i<=n;++i)
if(!use[i])
{
++sol;
dfs(i);
}
freopen("dfs.out","w",stdout);
printf("%d\n", sol);
return 0;
}