Pagini recente » shimulare | Cod sursa (job #814817) | Cod sursa (job #2368154) | Cod sursa (job #2201917) | Cod sursa (job #2225269)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int up[100010];
int h[100010];
bool viz[100010];
vector <int> adia[100010];
vector <vector <int>> comp;
void dfs(int nod, int tata = 0)
{
viz[nod] = 1;
up[nod] = h[nod];
for (auto i : adia[nod]) {
if (i == tata) {
tata = -1;
continue;
}
if (!viz[i]) {
h[i] = 1 + h[nod];
dfs(i, nod);
up[nod] = min(up[nod], up[i]);
}
up[nod] = min(up[nod], h[i]);
}
}
void divide(int nod, int c, bool tata = true)
{
viz[nod] = 0;
comp[c].push_back(nod);
for (auto i : adia[nod]) {
if (viz[i]) {
if (up[i] < h[nod] || (up[i] == h[nod] && !tata))
divide(i, c);
else {
comp.push_back({ nod });
divide(i, comp.size() - 1);
}
}
}
}
int main()
{
int n, m, a, b;
in >> n >> m;
while (m--) {
in >> a >> b;
adia[a].push_back(b);
adia[b].push_back(a);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
for (int i = 1; i <= n; i++) {
if (viz[i]) {
assert(i == 1);
comp.push_back(vector <int> ());
divide(i, comp.size() - 1, 0);
}
}
out << comp.size() << '\n';
for (auto i : comp) {
for (auto j : i)
out << j << ' ';
out << '\n';
}
return 0;
}