Pagini recente » Cod sursa (job #2818841) | Cod sursa (job #888653) | Cod sursa (job #172251) | Cod sursa (job #1962507) | Cod sursa (job #694436)
Cod sursa(job #694436)
#include<cstdio>
#include<vector>
#include<bitset>
using namespace std;
#define Nmax 100001
vector<int> G[Nmax];
bitset<Nmax> use;
//int T[Nmax], D[Nmax], F[Nmax], timp;
int N, M, nrcomp;
void DF(int nod) {
use[nod]=1;
//D[nod]=++timp;
//printf("%d ",nod);
for(vector<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
if(!use[*it]) {
//T[*it]=nod;
DF(*it);
}
//F[nod]=++timp;
}
int main() {
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int i, j;
scanf("%d %d",&N,&M);
while(M--) {
scanf("%d %d",&i,&j);
G[i].push_back(j);
G[j].push_back(i);
}
for(i=1; i<=N; i++)
if(!use[i]) {
DF(i);
++nrcomp;
//printf("\n");
}
/*for(i=1; i<=N; i++)
printf("%d ",T[i]);
printf("\n");*/
printf("%d\n",nrcomp);
return 0;
}