Pagini recente » Cod sursa (job #2970439) | Cod sursa (job #7199) | Cod sursa (job #93235) | Cod sursa (job #715288) | Cod sursa (job #2526617)
#define MAX_N 100000
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct Nod
{
Nod(int _nod) :
nod { _nod },
vecini { vector<Nod*>() }
{ }
int nod = 0;
vector<Nod*> vecini;
};
int n, m;
vector<int> G[MAX_N + 1];
bitset<MAX_N + 1> f;
Nod* C[MAX_N + 1];
Nod* Cicluri(int nodCur, int nodFin);
void Afisare(Nod* nodCur);
int main()
{
fin >> n >> m;
for (int i = 1, x, y; i <= m; ++i)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int nr = 0;
for (int i = 1; i <= n; ++i)
{
C[i] = Cicluri(i, i);
if (C[i] == nullptr)
{
nr += (int) !f[i];
continue;
}
nr += C[i]->vecini.size();
}
fout << nr << '\n';
for (int i = 1; i <= n; ++i)
{
if (C[i] == nullptr)
{
if (!f[i]) { fout << i << '\n'; }
continue;
}
for (const auto& v : C[i]->vecini)
{
fout << i << ' ';
Afisare(v);
fout << '\n';
}
}
fin.close();
fout.close();
return 0;
}
Nod* Cicluri(int nodCur, int nodFin)
{
Nod* res = nullptr;
bool ok = !f[nodCur];
f[nodCur] = true;
for (int v : G[nodCur])
{
if (v == nodFin)
{
if (res == nullptr)
{
res = new Nod(nodCur);
}
}
if (f[v]) { continue; }
Nod* pNod = Cicluri(v, nodFin);
if (pNod != nullptr)
{
if (res == nullptr)
{
res = new Nod(nodCur);
}
res->vecini.push_back(pNod);
}
}
if (ok)
{
f[nodCur] = res != nullptr;
}
return res;
}
void Afisare(Nod* nodCur)
{
if (nodCur == nullptr) { return; }
fout << nodCur->nod << ' ';
for (const auto& v : nodCur->vecini)
{
Afisare(v);
}
}