Pagini recente » Cod sursa (job #948937) | Cod sursa (job #3338834) | Cod sursa (job #3271125) | Profil Luncasu_Victor | Cod sursa (job #3337302)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector<vector<int>> adj_list;
vector<int> level, min_level, visited;
stack<pair<int, int>> st;
vector<vector<int>> comp;
void read()
{
fin >> n >> m;
adj_list.assign(n + 1, {});
level.assign(n + 1, 0);
min_level.assign(n + 1, 0);
visited.assign(n + 1, 0);
for (int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
}
void getComponent(int x, int y)
{
if (st.empty())
return;
vector<int> nodes;
auto [topx, topy] = st.top();
st.pop();
nodes.push_back(topx);
nodes.push_back(topy);
while (!st.empty() && (topx != x || topy != y))
{
topx = st.top().first;
topy = st.top().second;
st.pop();
nodes.push_back(topx);
nodes.push_back(topy);
}
comp.push_back(nodes);
}
void removeDup(vector<int> &v)
{
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
void dfs(int x)
{
min_level[x] = level[x];
visited[x] = 1;
for (auto &next : adj_list[x])
{
if (!visited[next])
{
st.push({x, next});
level[next] = level[x] + 1;
dfs(next);
min_level[x] = min(min_level[x], min_level[next]);
if (min_level[next] >= level[x])
{
// punct critic
getComponent(x, next);
}
}
else
{
if (level[next] < level[x] - 1)
min_level[x] = min(min_level[x], level[next]);
}
}
}
int main()
{
read();
for (int i = 1; i <= n; i++)
if (!visited[i])
dfs(i);
fout << comp.size() << "\n";
for (auto &c : comp)
{
removeDup(c);
for (auto &x : c)
fout << x << ' ';
fout << '\n';
}
return 0;
}