Cod sursa(job #991419)
Utilizator | Ilie Ovidiu Horatiu horatiu11 | Data | 30 august 2013 15:15:45 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
# include <cstdio>
# include <bitset>
using namespace std;
int n,m,i,k,viz[100001],x,y;
bitset <10001>G[10001];
void DFS(int x)
{
int i;
viz[x]=1;
for(i=1;i<=n;++i)
if(!viz[i]&&G[x][i]==1)DFS(i);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
G[x][y]=G[y][x]=1;
}
for(i=1;i<=n;++i)
if(!viz[i])
{
k++;
DFS(i);
}
printf("%d\n",k);
return 0;
}