Pagini recente » Cod sursa (job #471703) | Cod sursa (job #701214) | Utilizatori inregistrati la preONI 2007, Runda 4, Clasa a 9-a si gimnaziu | Cod sursa (job #1051077) | Cod sursa (job #916299)
Cod sursa(job #916299)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
vector<int> V[100000];
int Conexe;
int P[100000];
void Read()
{
fin >> N;
fin >> M;
int x, y;
for(int i = 1; i <= M; i++)
{
fin >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
}
void DF(int k)
{
P[k] = 1;
for(int i = 0; i < V[k].size(); i++)
if(P[V[k][i]] == 0)
DF(V[k][i]);
}
void Con()
{
for(int i = 1; i <= N; i++)
if(P[i] == 0)
{
Conexe++;
DF(i);
}
fout << Conexe;
}
int main()
{
Read();
Con();
fin.close();
fout.close();
return 0;
}