Pagini recente » Cod sursa (job #820979) | Cod sursa (job #2271303) | Cod sursa (job #2912135) | Cod sursa (job #2595514) | Cod sursa (job #754914)
Cod sursa(job #754914)
#include<fstream>
#include<vector>
#define Nmax 100010
using namespace std;
vector <int> muchii[Nmax];
int st[Nmax], viz[Nmax], k, i, n, m, x, y, ok1, ok, v, j, nr;
void dfs (int x)
{
st[1]=x;
viz[x]=1;
k=1;
while (k>0)
{
y=0;
v=st[k];
for (i=1; i<=n; ++i)
for (j=0; j<muchii[v].size(); ++j)
if (muchii[v][j]==i && viz[i]==0)
{
y=i;
break;
}
if (y==0)
k--;
else
{
viz[y]=1;
st[++k]=y;
}
}
}
int main()
{
ifstream f("dfs.in");
ofstream h("dfs.out");
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
nr=0;
ok=0;
while (ok==0)
{
ok1=1;
for (i=1; i<=n; ++i)
if (viz[i]==0)
{
ok1=0;
dfs(i);
nr++;
}
if (ok1==1)
ok=1;
}
h<<nr<<'\n';
return 0;
}