Pagini recente » Cod sursa (job #1903958) | Cod sursa (job #786793) | Cod sursa (job #1524923) | Cod sursa (job #2644094) | Cod sursa (job #2815205)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int N = 1e5;
int cc[N+1], n, m, ncc;
size_t poz[N+1];
vector <int> a[N+1];//listele de adiacenta
vector <int> c[N+1];//componentele conexe
ifstream in;
ofstream out;
int primul_vecin_nevizitat(int x)
{
while (poz[x] < a[x].size() && cc[a[x][poz[x]]] != 0)//caut primul vecin al lui x cu cc nul
{
poz[x]++;
}
if (poz[x] < a[x].size())
{
int y = a[x][poz[x]++];
return y;
}
return 0;
}
void dfs_it(int x)
{
stack <int> stiva;
cc[x] = ncc;
stiva.push(x);
while (!stiva.empty())
{
x = stiva.top();
int y = primul_vecin_nevizitat(x);
if (y == 0)
{
stiva.pop();
}
else
{
cc[y] = ncc;
stiva.push(y);
}
}
}
void dfs_rec(int x)
{
cc[x] = ncc;
for (auto y: a[x])
{
if (cc[y] == 0)
{
dfs_rec(y);
}
}
}
void componente_conexe()
{
for (int i = 1; i <= n; i++)
{
c[cc[i]].push_back(i);
}
for (int i = 1; i <= ncc; i++)
{
for (auto x: c[i])
{
out << x << " ";
}
out << "\n";
}
}
int main()
{
in.open("dfs.in");
out.open("dfs.out");
in >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (cc[i] == 0)
{
++ncc;
dfs_it(i);
//dfs_rec(i);
}
}
out << ncc << "\n";
//componente_conexe();
in.close();
out.close();
return 0;
}