Pagini recente » Cod sursa (job #38868) | Cod sursa (job #1188985) | Cod sursa (job #440018) | Cod sursa (job #1084845) | Cod sursa (job #1821731)
#include<stdio.h>
#include<vector>
#define MAXN 100001
FILE*fin,*fout;
inline void Adauga(int x,int lista);
void dfs(int nod);
std::vector<int> Lista[MAXN];
bool seen[MAXN];
int k;
int main()
{
fin=fopen("dfs.in","r");
fout=fopen("dfs.out","w");
int N,M;
fscanf(fin,"%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
int x,y;
fscanf(fin,"%d%d",&x,&y);
Adauga(x,y);
Adauga(y,x);
}
int ans=0;
for(int i=1;i<=N;i++)
{
if(!seen[i])
{
ans++;
seen[i]=1;
dfs(i);
}
}
fprintf(fout,"%d",ans);
fclose(fin);
fclose(fout);
return 0;
}
inline void Adauga(int x,int lista)
{
Lista[lista].push_back(x);
}
void dfs(int nod)
{
for(int i=0;i<Lista[nod].size();i++)
{
if(!seen[Lista[nod][i]])
{
seen[Lista[nod][i]]=1;
dfs(Lista[nod][i]);
}
}
}