Pagini recente » Cod sursa (job #3031748) | Cod sursa (job #867548) | Cod sursa (job #15671) | Cod sursa (job #2109237) | Cod sursa (job #2796960)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 10005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nrc; //nr comp conexe
int viz[N];
class Graph {
public:
int n; //nr de varfuri
int m; //nr de muchii
vector <int> a[N];
Graph(int n, int m)
{
this->n = n;
this->m = m;
}
void Citire_neorientat()
{
int i;
int x, y;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void DFS(int x);
/*void Citire_orientat()
{
int i;
int x, y;
for (i = 0; i < m; i++)
{
fin >> x >> y;
a[x].push_back(y);
}
}
void BFS(int x);
*/
};
/*void Graph::BFS(int x)
{
queue <int> q;
int k, i;
q.push(x);
bool viz[N] = { 0 };
int cost[N] = { 0 };
viz[x] = 1;
cost[x] = 0;
while (!q.empty())
{
k = q.front();
q.pop();
for (i = 0; i < a[k].size(); i++)
if (!viz[a[k][i]])
{
q.push(a[k][i]);
viz[a[k][i]] = 1;
cost[a[k][i]] = cost[k] + 1;
}
}
for (i = 1; i <= n; i++)
if (viz[i] == 0)
cout << -1 << " ";
else cout << cost[i] << " ";
}*/
void Graph::DFS(int x)
{
int i;
viz[x] = 1;
for(i = 0; i < a[x].size(); i++)
if (!viz[a[x][i]])
{
//viz[a[x][i]] = 1;
DFS(a[x][i]);
}
}
int main()
{
int n, m;
fin >> n >> m;
Graph g(n, m);
//g.Citire_orientat();
//g.BFS(S);
g.Citire_neorientat();
for(int i = 1; i <= n; i++)
if (!viz[i])
{
nrc++;
g.DFS(i);
}
fout << nrc;
return 0;
}