Pagini recente » Cod sursa (job #2918994) | Cod sursa (job #2594538) | Cod sursa (job #2439683) | Cod sursa (job #1862553) | Cod sursa (job #1382571)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
vector<int> v[100000];
int culoare[100000], parinte[100000], inceput[100000], sfarsit[100000];
queue<int> q;
int n, m, i, j, x, y, nod, sursa, contor_timp, k = 0;
void DFS(int nod)
{
contor_timp ++;
inceput[nod] = contor_timp;
culoare[nod] = 1;
for (i = 0; i < v[nod].size(); i++)
if(culoare[v[nod][i]] == 0)
{
parinte[v[nod][i]] = nod;
DFS(v[nod][i]);
}
contor_timp ++;
sfarsit[nod] = contor_timp;
culoare[nod] = 2;
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> n;
f >> m;
for(i = 1; i <= 100; i++)
{
culoare[i] = 0;
parinte[i] = 0;
inceput[i] = 0;
sfarsit[i] = 0;
}
contor_timp = 0;
for (i = 0; i < m; i++)
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
sursa = 1;
for(i = 0; i < v[sursa].size(); i++)
if(culoare[v[sursa][i]] == 0)
DFS(sursa);
for(i = 1; i <= n; i++)
if (culoare[i] == 0)
{
DFS(i);
k++;
}
g << k;
return 0;
}