Pagini recente » Cod sursa (job #1617382) | Cod sursa (job #603358) | Cod sursa (job #2293141) | Cod sursa (job #2402869) | Cod sursa (job #3222882)
#include<fstream>
#include<vector>
#include<set>
#include<stack>
#include<set>
#include<algorithm>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
std::vector<std::vector<int> > G;
std::vector<int> nivel, viz, nma;
std::set<int> puncteCritice;
std::vector<std::pair<int, int> > punti;
std::vector<std::set<int> > componente;
std::stack<int> dfsOrder;
int task, n, m;
void DFS(int start, int tata) {
viz[start] = 1;
dfsOrder.push(start);
nivel[start] = nivel[tata] + 1;
nma[start] = nivel[start];
int cnt = 0;
for(const int& x : G[start])
if (x != tata) {
if (viz[x]) {
if (nma[start] > nivel[x])
nma[start] = nivel[x];
}
else {
DFS(x, start);
++cnt;
if (nma[start] > nma[x])
nma[start] = nma[x];
if (nma[x] >= nivel[start] and start != 1)
puncteCritice.insert(start);
if (nma[x] > nivel[start])
punti.push_back(std::make_pair(x, start));
if (nma[x] >= nivel[start]) {
std::set<int> comp;
while (dfsOrder.top() != x) {
comp.insert(dfsOrder.top());
dfsOrder.pop();
}
comp.insert(x);
comp.insert(start);
dfsOrder.pop();
componente.push_back(comp);
}
}
}
if (start == 1 and cnt > 1)
puncteCritice.insert(1);
}
int main() {;
fin >> n >> m;
G.resize(n + 1);
nivel.resize(n + 1);
nma.resize(n + 1);
viz.resize(n + 1);
int x, y;
for (; m; --m) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1, 0);
fout << componente.size() << '\n';
for (const std::set<int>& S : componente) {
for (const int& x : S)
fout << x << ' ';
fout << '\n';
}
}