Pagini recente » Cod sursa (job #1999072) | Cod sursa (job #1883747) | Cod sursa (job #2744732) | Cod sursa (job #1490717) | Cod sursa (job #944110)
Cod sursa(job #944110)
#include<fstream>
#include<vector>
using namespace std;
int *vizitat;
int nrCompCon = 0;
void DFS(vector<int> *adj, int start)
{
int i;
for(i = 0; i < (int)adj[start].size(); i++)
{
if(vizitat[adj[start][i]] == 0)
{
vizitat[adj[start][i]] = 1;
DFS(adj, adj[start][i]);
}
}
}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, u, v, i;
fin >> n >> m;
vector<int> *adj = new vector<int>[n];
for(i = 0; i < m; i++)
{
fin >> u >> v;
u--;
v--; // retinem nodurile de la 0 la n - 1
adj[u].push_back(v);
adj[v].push_back(u);
}
vizitat = new int[n];
for(i = 0; i < n; i++)
vizitat[i] = 0;
for(i = 0; i < n; i++)
if(vizitat[i] == 0)
{
nrCompCon++;
vizitat[i] = 1;
DFS(adj, i);
}
fout << nrCompCon;
return 0;
}