Pagini recente » Cod sursa (job #356572) | Cod sursa (job #1726246) | Cod sursa (job #2176980) | Cod sursa (job #1296726) | Cod sursa (job #986558)
Cod sursa(job #986558)
#include <fstream>
#include <vector>
using namespace std;
#define nmax 100001
fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);
vector <int> A[nmax];
int dist[nmax];
bool viz[nmax];
int s[nmax],k;
int ras;
int N,M;
void DFS()
{
int x,z;
while(k>0)
{
x=s[k];
if(A[x].size() > 0)
{
z=A[x].size();
if(viz[A[x][z-1]] == 0)
{
viz[A[x][z-1]] = 1;
s[++k]=A[x][z-1];
dist[s[k]] = dist[x] + 1;
}
A[x].pop_back();
}
else k--;
}
}
int main()
{
int x,y,i;
fin>>N>>M;
/* k=1;
s[k]=1;
viz[1]=1;*/
for(i=1; i<=M; i++)
{
fin>>x>>y;
A[x].push_back(y);
A[y].push_back(x);
}
// DFS();
for(i=1; i<=N; i++)
{
if(viz[i]==0)
{
k=1;
s[1]=i;
viz[i]=1;
DFS();
}
}
for(i=1; i<=N; i++)
{
if(dist[i]==0) ras++;
// fout<<dist[i]<<' ';
}
fout<<ras;
fin.close(); fout.close();
return 0;
}