Pagini recente » Cod sursa (job #1606380) | Cod sursa (job #1701108) | Cod sursa (job #2519591) | Cod sursa (job #3031782) | Cod sursa (job #3270385)
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int v[2][1000000], start[1000000], c[1000000];
bool viza[100000];
int n, m;
void citire()
{
int k=0, x, y;
in>>n>>m;
for(int i=1; i<=m; i++)
{
in>>x>>y;
k++;
v[0][k]=x;
v[1][k]=start[y];
start[y]=k;
k++;
v[0][k]=y;
v[1][k]=start[x];
start[x]=k;
}
}
void dfs(int i)
{
int st=1, dr=1, man;
c[st]=i;
while(st<=dr)
{
man=start[c[st]];
while(man)
{
if(viza[v[0][man]]==0)
{
viza[v[0][man]]=1;
c[++dr]=v[0][man];
}
man=v[1][man];
}
st++;
}
}
int main()
{
int nr=0;
citire();
for(int i=1; i<=n; i++)
{
if(viza[i]==0)
{
viza[i]=1;
dfs(i);
nr++;
}
}
out<<nr;
return 0;
}